7.29：正睿集训（人工智能峰会）day2
今天，又重温了一下各种字符串的鬼畜算法，脑子仍是一团浆糊。
kmp,扩展kmp，AC自动机，后缀数组，后缀自动机，Manacher，广义后缀自动机…这其中，出来扩展kmp和广义后缀自动机我一无所知外，其他都是讲过的知识点，听得还不算自闭。
现在，就来小小地总结一下这些鬼畜算法的用处。
kmp：字符串匹配常用算法，其他字符串算法或多或少地都是由它发展而来。常用于难度较简单的字符串问题中。其常见用法有：
- 模式串与文本串的匹配。
- 有无重复字串及重复子串的大小。
- 处理前缀与后缀相关联的问题。
这三点是解决kmp题目中的常见切入点。
AC自动机：trie树与kmp的结合产物。将多个字符串存入trie树中。其常见用法有：
- 多模式串与文本串的匹配。
- 与DP相结合，每个点对应一种状态。
后缀数组：其用法后缀自动机都能代替。
后缀自动机：一种极其精妙的字符串算法。能在线性的时间与空间内构造出包含每一个子串的树形结构。其功能：
- 求子串出现个数。
- 求本质不同子串个数。
- parent树的妙用。
- endpos的妙用。
- 最长公共子串。
- 求第k大子串。
。。。。。。（此处省略一万字）。
睡觉去喽（瞌睡死了QAQ）。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！