[学习笔记]基础字符串算法
2022/2/21 14:26:35
本文主要是介绍[学习笔记]基础字符串算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
这里使用“基础”仅代表整合一些篇幅小的算法与后续几篇大的字符串算法文章区别。
留给自己补科技树的时间越来越短了。
字符串哈希
容易实现,可以快速比对两个串是否相等。
一般可以使用自然溢出\(Hash\)。
注意使用非自然溢出时,应当把膜数取比字符串数量高一个数量级的质数。
最小循环表示法
考虑有\(SAM\)构建的做法。
我们这里有一个简单做法,定义两个指针\(i = 1,j = 2\)。
两个指针不断向后匹配,直到两个字符不相等,假设前面相等的长度为\(k\),如果\(s[i + k] < s[j + k]\),则\(j = j + k + 1\),否则\(i = i + k + 1\),如果上述操作之后两个数相等,则强制一个向后移动。
具体实现则是:
点击查看代码
scanf("%lld",&n); for(int i = 1;i <= n;++i) scanf("%lld",&a[i]); for(int i = n + 1;i <= 2 * n;++i) a[i] = a[i - n]; int j = 1,i = 2,k,tmp; while(i <= n){ k = 0; while(a[i + k] == a[j + k]) k += 1; if(a[i + k] < a[j + k]) tmp = i,i = std::max(i + 1,j + k + 1),j = tmp; else i = i + k + 1; } for(int l = 1;l <= n;++l) std::cout<<a[j + l - 1]<<" "; }
KMP 算法
现在看KMP就觉得有新的理解。
我们现在发现求出的\(next\)实际是最长的border。
AC自动机
考虑实际上是在\(Trie\)上构建最长border树。
有三类题目:
首先是直接在自动机上匹配的问题。
第二类是在\(AC\)自动机上dp,这类问题是强制不能出现或者一定出现的题,可以直接在Trie图上跑,并记录状态即可。
第三类题目即使用\(fail\)树,其关键性质是所有有\(S\)作为子串的串都在其子树内,有意思的题即我前几天写的Salieri
这篇关于[学习笔记]基础字符串算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?