《中学生论文谈字符串匹配问题》由会员分享，可在线阅读，更多相关《中学生论文谈字符串匹配问题（22页珍藏版）》请在金锄头文库上搜索。
1、浅谈字符串匹配问题大丰市高级中学 吴悦欣引言在程序设计中，经常会出现字符串处理的题目，这一类题目重视选手的创新能力，无论对选手的代码能力异或是思维能力都有着比较高的要求。在此情况下，我们发现了很对处理字符串问题的强有力的工具，例如说KMP算法在线性时间内能够得心应手的处理两个字符串之间的匹配问题，后缀数组更是能够通过较低的复杂度处理很多字符串的操作，AC自动机更是可以轻松的处理多串匹配，字符串哈希效率高，编程复杂度低，性价比相当高。当然，具体的应用就该根据情况而定了。因为同学们对这些算法都很了解，介绍我就不多说了只是浅谈一下对这些算法应用的一些总结。目录Kmp算法应用列举后缀数组的一些应用AC
2、自动机的应用字符串哈希的应用一道例题浅谈比较Kmp算法应用列举直接利用next数组求解的：主要是求字符串的循环节、字符串子串与前缀的匹配问题。直接kmp匹配：这是最基础的，但是因为需要匹配的串的个数可能比较多，因此即使是线性算法，也免不了超时的悲剧。Kmp+树状数组：poj3167，是一道很经典的kmp好题，即两个字符串的匹配条件为对应的数的在串中排名对应相等。我们在进行kmp匹配的过程中可以时时用树状数组维护当前待匹配字符的排名。Kmp算法应用小结Kmp算法的很多应用其实都可以被后缀数组等代替，虽然是线性时间，但是在串数较多的情况下效果也并不是很好。充分了解next指针的一些性质也会有助于解
3、决kmp的题目，poj3167算是我看到过的最好的一道kmp题了，因为这充分利用了kmp两点匹配时的一些特性，通过数据结构顺利地解决了排名问题，这是后缀数组,AC自动机这些常用算法所做不到的。后缀数组的一些应用1：给你一个字符串，多次询问某两个后缀的最长公共前缀。解法：我们可以求得两个后缀的排名，只要通过RMQ求得两个后缀之间的height值的最小值。2：可重叠的最长重复子串问题。解法：因为可重叠，因此只需要在height数组中取一个最大值即可。后缀数组的一些应用3：不可重叠的最长重复子串问题。解法：这道题目复杂一点，需要先二分答案，然后问题就变为了判定性问题。即二分重复子串的长度L，那么我们
4、可以将排序后的后缀分为若干份，保证每一份中相邻后缀的最长公共前缀都大于等于L，那我们只需要分别在每组中都操作即可。因为不可重叠，所以每一组我们分别观察位置最靠前和最靠后的后缀，判断它们是否重叠，就可以求出解了。4：最长回文子串问题。解法：我们可以先添加要求的字符串S,再将S串翻转一下形成S，与串S之间加上一个连接将它们连接起来，并求出该串的后缀数组。枚举中心位置的时候，相当于是要求出以枚举的该点为起点的两个后缀的最长公共前缀。后缀数组的一些应用5：多个串最长公共子串问题。解法：因为每一个子串必定是一个后缀的前缀，我们可以依旧将这些串接在一起，相邻两个串之间插入一个分隔符。接下来就简单了，求出了
5、后缀数组之后，我们可以二分子串的长度，然后依据height分为若干段，只要有一段中包含了所以询问串，那么就是可行解了。6：重复次数最多的连续重复子串问题解法：我们可以先暴力重复子串的长度L，然后我们可以将这个串分为1.L,l+1.2L这些块。一个重复次数大于1的串必定包含若干个这样的块，这些块也一定是相等的。那么我们可以枚举起点的一个块，然后得到接下来和它相等的块的个数，再左右调整是否还有被分割下来的匹配块，就可以了。后缀数组应用小结后缀数组的应用范围非常广，我只列举了少部分比较经典的。实质上后缀数组在应用过程中不外乎借助于height数组、RMQ算法、二分等辅助算法。在处理多串匹配问题时我们
6、也可以将待匹配的串接在一起。只要我们能够充分了解这些算法的性质，就可以很好的解决这些问题了。AC自动机的应用最基础的做法：即直接建立ac自动机，然后用母串进行匹配。这样可以很好的解决多串匹配的问题，时间复杂度很低。AC自动机+DP：这是非常经典的用法，因为可以根据AC自动机上的每一个点设计状态，表示当前匹配字符串的情况，然后可以依据题目中的需要进行转移即可。DP有时因为转移次数较多也需要通过矩阵优化。通过fail指针：因为Fail指针的性质，我们可以根据fail指针建树，通过这个树的dfs序或是其他的一些性质，也可以很好的解决一些问题，如noi2011的阿狸的打字机。AC自动机应用小结AC自动
7、机在多串匹配的题目非常有用，正常和dp算法一起使用。在实际应用中需要很好的了解fail指针的相关性质。字符串哈希的应用字符串哈希主要应用于判断两个字符串是否相等。因求两个串完全匹配的时候预处理O(n)，匹配的复杂度只要O(1)，可以很好得代替kmp方法。在求后缀数组时，可以直接对所有后缀进行快排，比较函数可以借助于字符串哈希二分两个后缀相同的位置，从而得出两个后缀的大小关系。字符串哈希的应用此外，字符串哈希在很多题目中都有着很广泛的应用，如可以利用字符串哈希可以通过二分求出以某个点为中心的最大回文串，从而得到这个串的最大回文子串。复杂度为O(nlogn)，时间复杂度和后缀数组相同，代码量却简单
8、得多。spoj8093题目描述给你n个句子和m个单词，问每个单词在多少个句子中出现过（同一个句子不重复计算）。句子的总长度在100000以内，单词的总长度在360000。初步想法这道题目最暴力的方法就是每一个单词都和每一个句子运用kmp匹配，然后统计结果就可以了。复杂度较大，显然过不掉。因为这道题涉及多串匹配，我们考虑使用ac自动机。Ac自动机具体做法比较简单，实践也不复杂。显而易见，我们能够将所有单词建立AC自动机，然后对于每一个句子，我们将它在自动机上走一遍，就可以知道一些到达的点，然后将这些到达的点按照fail指针走一遍就可以知道所有可以到达的点，对于每一个经过的点都标记一下。最后结果自
9、然就是查看每一个单词的末尾被多少个句子遍历过。Ac自动机本来用fail指针感觉复杂度很高，但又构造不出针对性数据，因此总的效率还是很客观的。具体复杂度的估算或是针对性数据欢迎大家提出来。后缀数组我们先将所有的单词和所有的句子连接在一起，中间用分隔符分割。然后我们便求出这一个大串的后缀数组。对于每一个单词，我们可以根据后缀数组和height数组得出那些前缀为该单词的后缀，显然这些后缀的排名都是连续的。那么实际上每一个单词需要询问的就是这一段区间中有多少个不同的句子（后缀开头所在的句子），因此假设每一个句子都有一个值，那么就变成询问一段区间总共有多少不同的数。后缀数组这个问题有一个非常方便的离线算
10、法，即把所有的询问按照右端点排序，然后我们一次扫描每一个点，一个点可以作为合法点当且仅当这个点被扫描过且下一个表示该句子的点没有被扫描过。我们可以用树状数组维护区间合法点的个数，做询问即是统计这段区间内合法点的个数，这也就是最终的答案。因为后缀数组的复杂度是O(LlogL)，而离线操作的复杂度为(nlogn)，所以总的复杂度为O（LlogL+ nlogn）。本题小结这道题目可以较鲜明得看出这三个算法的一些联系与区别，kmp做多串匹配的时间复杂度是一个不小的问题。ac自动机善于解决多串匹配，复杂度很低，但是也有局限性。后缀数组和很多算法结合在一起，综合考察了选手对这些算法的掌握。总结本文所总结的几个算法在字符串匹配问题中应用很广，都已经烂大街了。但是当然了，还有很多其他的算法。比如后缀树，还有一个很强的后缀自动机（代码各种简单，但各种难理解），可以解决很多问题。在面对实际的问题时，应该充分把握问题的特殊性质，只要熟悉这些算法的应用，相信就可以熟练地解决这一类问题了。The endThank you
