字符串算法集合

1、字符串相关算法字符串相关算法 KMP（KMP和扩展和扩展KMP） Trie树树 AC自动机自动机 Trie图图 Suffix Array(后缀数组）后缀数组） 字符串字符串HASH(Rabin Karp、 ELF Hash) 字符串循环最小表示字符串循环最小表示 BM(Boyer-Moore)算法算法目目录录KMPKMP算法算法简介 KMP算法是用于处理字符串匹配的高效算法 给定两个字符串，判断B串是否是A串的子串（即A串是否包含B串） 在一个长字符串中匹配一个短子串的无回溯算法朴素算法 枚举A串中的每个字符，将起作为起点，将其与B串中的字符进行一一比较 For (I = 0 ; i strl

2、en(A); I +) For ( j = 0 ; j strlen(B); j +) if (Bj!=Ai+j) break; if (j=strlen(B) return yes; 复杂度 设A串（主串）长度为n，B串（模式串、匹配串）长度为m 朴素算法为枚举A串的每个字符为起点看是否包含B串，复杂度为O（m * n） KMP算法复杂度O（m + n） KMP工作过程 用两个指针i和j分别表示，Ai-j+ 1.i与B1.j完全相等 i是不断增加的，随着i的增加j相应地变化，且j满足以Ai结尾的长度为j的字符串正好匹配B串的前 j个字符 KMP工作过程 Ai+1 = Bj+1 ，i + ，j

3、 + Ai+1 != Bj+1 ，j减小，i不变，使得出现新的j，满足Ai结尾的长度为j的字符串正好匹配B串的前 j个字符 这时匹配的字符的个数已减少，相当于位置的移动KMP工作过程 例 1 2 3 4 5 6 7 8 9 A = a b a b a b a a b a b B = a b a b a c b 1 2 3 4 5 6 当i = 5 ， j = 5时，出现Ai+1 != Bj+1 ，j应当变小，从而实现新的匹配KMP工作过程 此时，A6B6。这表明，此时j不能等于5了，我们要把j改成比它小的值j。j可能是多少呢？仔细想一下，我们发现，j必须要使得B1.j中的头j个字母和末j个字母

4、完全相等（这样j变成了j后才能继续保持i和j的性质）。 KMP工作过程 例 1 2 3 4 5 6 7 8 9 A = a b a b a b a a b a b B = a b a b a c b 1 2 3 4 5 6 j由5变为3，使得A35与B13匹配，然后再按照刚才算法继续执行KMP工作过程 定义next数组记录当在j位置出现不匹配的时候j应该改变的值，当出现不匹配的时候令j = nextj; 设A串长度为lena，B串长度为lenb，则整个计算过程如下：伪代码 for (i = j = 0; i lena & j lenb; ) if(j 0 | Ai = Bj)i +, j +;

5、elsej = nextj; Next从何而来 Next数组很好很强大，可是它要怎么来呢？ 直观的看，j应该是能满足Ai结尾的长度为j的字符串正好匹配B串的前 j个字符的尽量大的值 实际上，B串建立next的过程和主串寻找匹配的过程是一样的Next数组的含义设nexti=j这意味着对于串B来说B1B2Bj=Bi-j+1BjNext寻找过程 如果Bk = Bj，k j，则可以令nextj +1 = k + 1，否则另k = nextk，然后再看新的Bk和Bj是否匹配 令最初的next0 = -1作为入口，则建立next的过程如下Next寻找过程 int j = 0, t = next0 = -1

6、; while(j lenb - 1) if(t 0 | Bj = Bt)next+ j = + t;elset = nextt; 百科名片 KMP算法是通过分析子串，预先计算每个位置发生不匹配的时候，所需GOTO的下一个比较位置，整理出来一个next数组，然后在上面的算法中使用。 ProblemPKU 2185 给出一个字母组成的矩阵，找出一个最小的子矩阵，使得这个子矩阵的无限复制扩张之后的矩阵包含原来的矩阵，例如 ABABA ABABA 其最小重复子矩阵是ABl解法求出每一行的最小重复串长度，所有行的最小重复串的长度的lcm就是最小重复子矩阵的宽；求出每一列的最小重复串长度，所有列的最小重

7、复串的长度的lcm就是最小重复子矩阵的长。l最小重复串长度？利用KMP得到P数组串长-末位的P值扩展的扩展的KMPKMP算法算法樊向宇樊向宇【扩展的【扩展的KMP算法】算法】扩展的扩展的KMPKMP问题：问题：给定母串S，和子串T。 定义n=|S|, m=|T|，extendi=Si.n与T的最长公共前缀长度。请在线性的时间复杂度内，求出所有的extend1.n。容易发现，如果有某个位置i满足extendi=m，那么T就肯定在S中出现过，并且进一步知道出现首位置是i而这正是经典的KMP问题。 因此可见“扩展的KMP问题”是对经典KMP问题的一个扩充和加难。 例子 S=aaaaaaaaaabaa

8、a, T=aaaaaaaaaaa。extend2=9。为了计算extend2，我们是不是也要进行10次比较运算呢？不然。因为通过计算extend1=10，我们可以得到这样的信息： S1.10=T1.10 S2.10=T2.10。计算extend2的时候，实际上是S2开始匹配T。因为S2.10=T2.10，所以在匹配的开头阶段是“以T2.10为母串，T为子串”的匹配。 设辅助函数nexti表示Ti.m与T的最长公共前缀长度。 对上述例子，next2=10。也就是说： T2.11=T1.10 T2.10=T1.9 S2.10=T1.9。这就是说前9位的比较是完全可以避免的！我们直接从S11T10开

9、始比较。这时候一比较就发现失配，因此extend2=9。 下面提出一般的算法。 设extend1.k已经算好，并且在以前的匹配过程中到达的最远位置是p。最远位置严格的说就是i+extendi-1的最大值，其中i=1,2,3,k；不妨设这个取最大值的i是a。(下图黄色表示已经求出来了extend的位置)第一种情况第一种情况第二种情况第二种情况 整个算法描述结束。 上述算法是线性线性算法。原因如下： 容易看出，在计算的过程中，凡是访问过的点，都不需要重新访问了。一旦比较，都是比较以前从不曾探访过的点开始。因此总的时间复杂度是O(n+m),是线性的。如何求解如何求解next数组数组还剩下一个问题：n

10、ext这个辅助数组怎么计算？复杂度是多少？我们发现计算next实际上以实际上以T为母串、为母串、T为子串的一个特殊为子串的一个特殊“扩展的扩展的KMP”。用上文介绍的完全相同的算法计算next即可。（用next本身计算next，具体可以参考标准KMP）此不赘述。总结总结 算法的思想 已经访问过的点绝不再访问，充分利用已经访问过的点绝不再访问，充分利用已经得到的信息。已经得到的信息。扩展扩展KMP的一些应用的一些应用 求解最长公共前缀长度 求字符串中重复子串的长度 （利用next数组，nexti表示Ti.m与T的最长公 共前缀长度。 找重复子串 ，比如abababccc ，ababab就是重复子

11、串；再比如 ababa，这个也是重复的，只是最后一个循环节不完整，端点处的循环节不完整的串也算作重复串。 因此i+nexti的长度就是重复子串的长度。） 例如poj2185 比如ababab ，next2 = 4， 2，3匹配0，1 ；然后4，5匹配2，3；相当于还是匹配0，1 ；所以0，1被重复了3次，所以只要是能匹配上的，就是在重复前i个字符 ，能匹配多长，就是重复了多长，直接用i+nexti就是最长的长度 。求解extend数组的模板void GetExtand(const EleType str, int strLen, int extand, const EleType mode,

12、int modeLen, int next) int i, a, p, j(-1); for (i = 0; i strLen; +i, -j) if (j = p) if (j 0) j = 0, p = i; while (p strLen & j modeLen & strp = modej) +p, +j; extandi = j, a = i; else extandi = nexti - a; 根据上面的模板，大家可以仿照写计算next的函数。 poj2185主要求解next数组，唯一的不同在于此题是一个二维char数组，我们可以先把每一列看作一个点，这样整个二维数组看成一个字符串

13、，算出nexti;在把每一行看作一个点，又一个字符串，再求出一组nexti。这两个过程中，分别对求出来的nexti,根据i+nexti=len（表示循环长度覆盖了整个串），进行判断筛选，将行与列的结果进行组合，即求得可行解。（题目要求的是面积）TRIETRIE树树樊向宇樊向宇Trie树 字典树 空间换时间 引入问题：对于包含100000个长度不超过10的单词组成的字典库，给定任意一个单词，判断其是否为字典库中某个单词的前缀 给定b，abc，abd，bcd，abcd，efg，hii，建立Trie树如下结点Struct nodeint nextMAX_N; /指向子节点bool end;/标记单词

14、末尾Problem 现有4000个单词组成的词库，每个单词长度不超过100。给定一字符串，长度不超过300000，要求将字符串分割为词库中的单词，问有多少种方法。 Sampleabcd ans=24abcdabACAC自动机自动机樊向宇樊向宇AC自动机 设共有设共有m个模式串，长度分别为个模式串，长度分别为L1、L2Lm正文为一个长度为正文为一个长度为n的数组的数组T1.n，限定，限定900Kn,1000m,100KL朴素算法 从小到大枚举每一个位置，并且对所有模式从小到大枚举每一个位置，并且对所有模式串进行检查。最坏情况下时间复杂度为串进行检查。最坏情况下时间复杂度为 对每一个模式串，使用对

15、每一个模式串，使用kmp算法进行单串匹算法进行单串匹配，时间复杂度为配，时间复杂度为)Ln(O)Lmn(O前缀指针 KMP中我们用两个指针i和j分别表示，Ai-j+ 1.i与B1.j完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以Ai结尾的长度为j的字符串正好匹配B串的前 j个字符，当Ai+1Bj+1，KMP的策略是调整j的位置（减小j值）使得Ai-j+1.i与B1.j保持匹配且新的Bj+1恰好与Ai+1匹配（从而使得i和j能继续增加）。 Trie树上的前缀指针与此类似。假设有一个节点k，他的前缀指针指向j。那么k,j满足这个性质：设root到j的距离为n，则从k之上的

16、第n个节点到k所组成的长度为n的单词，与从root到j所组成的单词相同。生成前缀指针 root及其儿子的前缀指针指向root 对于每个节点：设这个节点上的字母为C，沿着他父亲的前缀指针走，直到走到一个节点，他的儿子中也有字母为C的节点。然后把当前节点的前缀指针指向那个字母也为C的儿子。如果一直走到了root都没找到，那就把前缀指针指向root BFS匹配过程初始Trie中有一个指针t1指向root，待匹配串中有一个指针t2指向串头。接下来的操作和KMP很相似：如果t2指向的字母，是Trie树中，t1指向的节点的儿子，那么t2+1,t1改为那个儿子的编号，否则t1顺这当前节点的前缀指针向上找，直

17、到t2是t1的一个儿子，或者t1指向根。如果t1路过了一个绿色的点，那么以这个点结尾的单词就算出现过了。或者如果t1所在的点可以顺着前缀指针走到一个绿色点，那么以那个绿点结尾的单词就算出现过了。 注意传递性注意传递性自上至下标记自上至下标记zababaabcbabaaabaProblem 给定10000个长度不超过50的关键词，对于一长度不超过1000000的字符串，求其中出现了多少种关键词？TrieTrie图图樊向宇樊向宇Trie图 Trie图是AC自动机的扩展，每个节点对于字符集中的所有字符均存在一个指针 建图流程建立Trie 树生成前缀指针补齐所有边 前缀节点的求法与AC自动机相同 补边

18、的方法为： 从根结点出发的补边指向根本身； 对非根结点x，若它没有c孩子，则新建一条边，从x指向x的后缀结点的c孩子。 处理某个结点的过程中需要用到深度比它小的结点的后缀结点及各个孩子。由于我们按层次遍历trie树，这些信息都已求得。Trie图的构建（构建流程演示）结点前缀a孩子b孩子c孩子001491012924573391049405795112669104974578891049901049101129501942107863abcbcaccba图例：安全结点危险结点cbcabababacabcProblem 给出n(n=10)个长度不超过的恶性DNA片段，要求构造长度为m(m=2000

19、000000)的DNA序列，使其不包含恶性DNA片段，求构造方法总数Sample Input4 3ATACAGAASample Output36Problem DNA Repair给出n(1=n=50）个长度不超过20的恶性DNA片段，对于一个长度为m(1=m=1000)的DNA序列，通过改变最少的字符使其不包含恶性片段。Sample Input2AAA AAG AAAGSample Output1Suffix Suffix ArrayArray( (后缀数组）后缀数组）樊向宇樊向宇后缀数组 对字符串的所有后缀按字典序排序，将各后缀的起始位置按排序后的顺序摆放得到后缀数组SA。 RANK数组与

20、SA相对应，Ranki保存Suffix(i)在排序中的名次SA构造方法 倍增算法 DC3算法倍增算法对字符串u，定义uk =u1.k,len(u)ku ,len(u)k定义k-前缀比较关系k，=k和k对两个字符串u,v，ukv当且仅当ukvku=kv当且仅当uk=vkukv当且仅当ukvk倍增算法uvukv？u=kv？ukv？kuvu2kv？u=2kv？u2kv？kk后缀数组构造方法设u=Suffix(i)，v=Suffix(j)后缀u，以i开头后缀v，以j开头对u、v在2k-前缀意义下进行比较kkkk比较红色字符相当于在k-前缀意义下比较Suffix(i) 和 Suffix(j)比较绿色字符

21、相当于在k-前缀意义下比较Suffix(i+k) 和 Suffix(j+k)在2k-前缀意义下比较两个后缀可以转化成在k-前缀意义下比较两个后缀i+kj+k后缀数组构造方法把n个后缀按照k-前缀意义下的大小关系从小到大排序将排序后的后缀的开头位置顺次放入数组SAk中，称为k-后缀数组用Rankki保存Suffix(i)在排序中的名次，称数组Rankk为k-名次数组后缀数组构造方法利用SAk可以在O(n)时间内求出Rankk利用Rankk可以在常数时间内对两个后缀进行k-前缀意义下的大小比较后缀数组构造方法如果已经求出Rankk可以在常数时间内对两个后缀进行k-前缀意义下的比较可以在常数时间内对

22、两个后缀进行2k-前缀意义下的比较可以很方便地对所有的后缀在2k-前缀意义下排序采用快速排序O(nlogn)采用基数排序O(n)可以在O(n)时间内由Rankk求出SA2k也就可以在O(n)时间内求出Rank2k 后缀数组构造方法1-前缀比较关系实际上是对字符串的第一个字符进行比较可以直接根据开头字符对所有后缀进行排序求出SA1采用快速排序，复杂度为O(nlogn)然后根据SA1在O(n)时间内求出Rank1可以在可以在O(nlogn)时间内求出时间内求出SA1和和Rank1后缀数组构造方法直接根据首字符排序SA1Rank1O(nlogn)SA2Rank2O(n)SA4Rank4O(n)SA8

23、Rank8O(n)O(n)SAmRankmO(n)m=2t且mnO(nlogn)的操作一次O(n)的操作logn次总复杂度为O(nlogn)后缀数组辅助工具仅仅靠后缀数组和名次数组有时候还不能很好地处理问题后缀数组的最佳搭档LCP定义两个字符串的最长公共前缀Longest Common Prefixlcp(u,v)=maxi|u=iv也就是从头开始比较u和v的对应字符持续相等的最远值后缀数组辅助工具定义LCP(i,j)=lcp(Suffix(SAi),Suffix(SAj)也就是SA数组中第i个和第j个后缀的最长公共前缀LCP Theorem对任何1i1 且Ranki1，一定有hihi-1-1

24、后缀数组辅助工具当hi-11 时，hi0hi-1-1。当hi-11时，令j=i-1,k=SARankj-1。显然有Suffix(k)1 和Suffix(k)Suffix(j)：lcp(Suffix(k+1),Suffix(i)=hi-1-1。Rankk+1wj+k，同理可以讨论ui+kwj+(x-i)j+k。1ixu：i+ki+k+1 |s1|1w：jj+(x-i)j+kj+k+1 |s2|大于s1(x-1)的前几个字符一定是s1的其他循环表示的前几个字符所以s1(x-1)不可能是s1的最小表示！因此M(s1)i+k，指针i滑到ui+k+1处仍可以保证小于等于M(s1)！“最小表示法”在本题的应用同理，当ui+kwj+k的时候，可以将指针j滑到wj+k+1处！也就是说，两指针向后滑动比较失败以