实用字符串算法小结.docx

LBoy- 39 / 39实用字符串算法2最小表示法2最小表示法算法的思想2最小表示法的基本操作3最小表示法的时间复杂度度4最小表示法的应用：4判定两个给定串，是否同构？4求一个串的最小字典序的起始位置4KMP算法4KMP算法的思想4KMP算法的基本操作：5KMP算法的复杂度5KMP算法的应用：5next 索引向量在解决最小重复、不重叠子串中的应用：5求两个字符串的最短和串，即两个字符串的最短母串，容许发生覆盖。7最长、短公共子串Longest Shortest Common Substring.7单模式串在主串中匹配的问题。7定义匹配模式匹配问题8利用她前缀自动机的思想解题8利用她前缀自动机的思想进行DP9extend-kmp 扩展KMP算法10ExtendKmp的应用：11求一个串的最长回文串的长度11Trie树12Trie树 又称单词查找树，字典树12基本操作12Trie树的基本结构12Trie树的应用13AC自动机13ac自动机13AC自动机的应用：15普通多模式匹配问题15重叠与不重叠多模式匹配问题15自动机 DP 关键自动机上状态转移15通配符匹配问题。对于这类问题，我有时间会做一个专题，现在仅贴一个题目。17trie图18Trie图与AC自动机的本质区别18Trie图算法的总述：18The C code Trie图的改进后的基本操作20Trie图的应用：22安全图的状态变换。22写这个总结，对我来说，是酝酿已久的，从我看完常用的字符串的算法之后，就像总结一下，为了自己用也好，算是留给队里的贡献也罢。原计划是花十天左右的时间，现在只能用一天一夜来完成这份工作，不知道结果能否令我满意。且不说结果了，赶紧开始实用字符串算法字符串算法是信息学竞赛里面很重要的一个分支， 其题目特点是相对来说比较简单，但是却不容易想到。字符串处理的算法有很多，我这里主要简单的介绍的mp、kmp、extend_kmp、后缀数组、tire树、tire图，后缀树（引入思想） 以上面的这张图简单的介绍这几种算法最小表示法最小表示法算法的思想 “最小表示法”是判断两种事物本质是否相同的一种常见思想。对于我们要处理的字符串来说，给定两个长度相等的字符串，|s1|=|s2|，判断它们是否是循环同构的。图1-0最小表示法的基本操作最小操作算法在处理字符串时，常常是用来求解原序列字典序最小的同构的起始位置，下面是求起始位置。const int maxn = 10001;char smaxn;int minExpress(char *s, int len) int i = 0, j = 1, k = 0, t; while(i len & j len & k 0) i += k + 1; else j += k + 1; if (i = j) j+; k = 0; return min(i, j)+1;判定两个给定的字符串是否同构,其中i,j两个指针分别指向出现最小同构的s和t起始位置。const int maxn = 10001;char smaxn, tmaxn;int minExpress(char *s, int slen, char *t, int tlen) if(slen != tlen) return 0; int i = 0, j = 0, k, tmp; for(k = 0; k slen; k+) /加倍字符串。 sslen + k = sk, ttlen+k = tk; sslen1 = ttlen1 = k = 0; puts(s); puts(t); while(i slen & j tlen & k 0) i = i + k + 1; else j = j + k + 1; k = 0; / printf(i=%d, j = %dn, i, j); return k = slen;知道了起始位置，我们可以一个遍历求出最小同构串。最小表示法的时间复杂度度：不用预处理，在判读两个串是否同构的时间复杂度为O(N)最小表示法的应用： 判定两个给定串，是否同构？在这里，是最基本的应用，要比KMP算法来的高效，因为没有预处理的时间。在这里，我们要借助两个指针，分别指向两个串s, t,匹配的起始位置，详细过程和大家见上。（题目略） 求一个串的最小字典序的起始位置TJU_3275_Windys S： link: /toj/showp3275.html zju_2006_Glass Beads zju_1729_Hidden Password pku_3349_Snowflake Snow Snowflakes 注意顺时针和逆时针hdu3374 String Problem 求出最小位置，最大位置对串中的每个元素取负。kmp判断子串重复度。hdu_2609_How many pku_3581_KMP算法 KMP算法的思想 是一种基于前缀搜索的方字符串处理方法的一种算法，核心思想是：找到一种有效的机制来计算已读入文本的后缀也是模式串p的前缀的最长字符串，并且对每个字符而言，最好是常数的均摊时间。（另外一种直观的理解就是，要充分利用上一次的匹配结果，找到匹配失败时，模式串可以向前滑动的最大距离,也就是next的值）图2-1我们可以用后缀限制自动机的观点来理解，自动机中对应节点后缀指针就是next函数值。（仔细分析这个图：我们定义了根节点的next0 = -1,而以后第k个字符（从第零开始算起）对应的失败指针（如果匹配到当前位置，匹配失败后的指向或者接下来继续匹配的位置）为nextk.由此，我们可以很好的理解next函数的性质：利用已读入文本的后缀和模式串p的前缀进行匹配。下面的图是改进后的KMP算法的模型。图2-2KMP算法的是由Morris 和Pratt提出，有knuth提出的改进算法：两种算法都有各自的用途，1. 如果要用到匹配，建议用KMP算法。（路径压缩的，可以避免不必要的匹配，向前滑动最远的距离）2. 如果用不到文本匹配，仅仅考虑的next指针求解，用MP算法。（不含路径压缩，更能体现指针的过程）。KMP算法的基本操作： const int maxm = 100; / 模式串的最大长度const int maxn = 1000000; / 文本的最大长度(离线的）char pmaxm, tmaxn;int n, m, nextmaxm;void getNext(char *p, int m, int *next) int i = 0, j = next0 = -1;while(i m) if (j = -1 | pi = j) /next+i = +j; / Morris & Pratt的算法+i; +j;nexti = pi != pj ? j:nextj; / Knuth的思想 elsej = nextj;/while/for(i=0; i=m; i+)printf(next%d=%dn,i,nexti);/校验/ getNext。/ 匹配成功，返回一次匹配成功的在文本中的起始位置；否则，-1；int kmpIndex(int pos) int i = pos, j = 0;while(i n & j = m ? (i-m):-1;/ 返回模式串在文本中出现的次数。(前后两次出现允许重叠)int kmpIndex() int i = 0, j = 0, ret = 0;while(i n & j = m) ret+; j = nextj;/whilereturn ret;KMP算法的复杂度：KMP在预处理阶段的时间复杂度为O(m),在搜索阶段的时间复杂度为O(n). 故，O(N+M)KMP算法的应用： next 索引向量在解决最小重复、不重叠子串中的应用：由定义：next向量里面的每个元素保存的都是前一个字符匹配成功或失败之后的下一个位置结论：已知字符串t第k个字符的nextk. 设d = k - nextk.如果k%d = 0 那么t1.k最多可以均匀的划分为k/d份。也就是可以生成一个长度为d的重复度为k/d的一个子串。解决这类问题，我们可以用MP(Morris-Pratt) Algorithm.因为不涉及两个串的匹配。第一个假设：假设我们的字符串为S,其长度为length,我们最多可将它平均分为n份，每份长度为k,(注意这里假设了length%n=0, 这个假设却未必成立)，那么我们将S分为了t0 t1 t2 .t(n-1) 每份t长度为k.(这里我们可以理解为循环节)第二个假设：由kmp算法的方法，设nextlength=x; 那么有s0 s1 . sx sx+1 . slength-1 slength 加上前面均分为n份的假设, k=length-x;那么假设可以均分,显然slength的值最好配到了tn-1的第一个字符，我们将其写为t0 t1 t2 t3 . t(n-1) null结束符t0 t1 t2 . t(n-2) 按kmp的匹配法则，有t1=t0 t2=t1 t3=t2 . t(n-1)=t(n-2) 找一个字符串s的最小重复不重叠子串subs。Sorce: 12/JudgeOnline/problem?id=2406 找一个字符串s的某个前缀的最小重复不重叠子串subsSorce: 12/JudgeOnline/problem?id=1961 以上两类问题我们都可以用MP(Morris & Pratt) Algorithm来解决。对于第一类问题，我们还可以用KMP(Knuth-Morris-Pratt)来处理，但是额外的增加啦比较的次数。 找一个字符串s的所有的前缀和后缀相等的子串。MP算法的核心就是找一个字符串的后缀和前缀相等的子串。这是对定义的一个简单考察。不过，要充分的熟悉next索引向量的求解过程。分析一个例子：第一次比较 “a b a b c a b a b”和 “ a b a b c a b a b”第二次比较 “a b a b” 和“ c a b a b ” / 和 “ a b a b c a b a b”第三次比较 “a b”和“ a b” /和“ c a b a b ”/ 和 “ a b a b c a b a b”第四次比较 “a ”和“b” /和“ a b” /和“ c a b a b ”/ 和 “ a b a b c a b a b”核心代码：(这里我们充分利用啦字符串的对称性） 1 求出所有的next. 2 然后由后往前进行枚举，枚举的过程不断缩小比较的字符段。（这里我们每必要在保留next数组.)int k = s.len+1;for (int i = s.len; i = 0; i = nexti) nextk- = i; if (s.stri-1 != s.strnexti-1) break; / for_iSorce: 12/JudgeOnline/problem?id=2752 告诉一个字符矩阵，找一个子矩阵： 要求： 1 子矩阵经过多次重复之后可以覆盖掉原字符矩阵。 2 输出子矩阵的元素的个数。对于一个看起来摸不着头脑的题目，我们可以将它划分。考虑整个矩阵或许很困难，那我们就先考虑行，然后用类似的思想考虑列。 让我们先分析几个例子： (1) ABAB 2 ABAB 2 1111 lcm(2, 2) * lcm(1,1,1,1) = 2 = len(AB) (2) ABABAB 2 ABCABC 3 112222 lcm(2, 3) * lcm(1,1,2,2,2,2) = 6 * 2 = 12 = 原矩阵 (3) ABABC 5 ABABC 5 11111 lcm(5,5) * lcm(1,1,1,1,1) = 5 * 1 = 5 = len(ABABC) (4) ABAB 2 CDCD 2 BABA 2 DCDC 2 4444 lcm(2,2,2,2) * lcm(4,4,4,4) = 2 * 4 = 8 (5) ABCABCA 3 BACBACB 3ABCABCA 3BACBACB 3ABCABCA 3 ABC 2222222 lcm(3,3,3,3,3) * lcm(2,2,2,2,2,2) = 2 * 3 = 6 BAC分析上面的例子我们可以看到：结论：一个字符矩阵的最小重复矩阵等于各行的最小公倍子串 * 各列的最小公倍子串。 接下来我们要考虑的就是如何快速的求的各行（列）的子串，首先我们要找的是各行（列）的最小子串，这里有和以往的有所不同，分析例子5我们就可以看到哦。这里有一个覆盖的问题，就是最后的A或B可能为字符串的前缀这里应视为包含在ABC里. 因此，如何求的一行（列）的最小子串，称为解决此题的关键所在。 现在我们分析串： A B C A B C A B -1 0 0 0 1 2 3 4 5这里我们要利用kmp算法匹配的next数组，nextn 保存的是最后一次匹配成功的位置。我们只要n - nextn.就看算出匹配的子串的长度。（后附代码附录一）Sorce：12/JudgeOnline/problem?id=2185 通过这题我们也可以发现对原结论的一个补充：结论：已知字符串t第k个字符的nextk. 设d = k - nextk.如果k%d = 0 那么t1.k最多可以均匀的划分为k/d份。也就是生成一个长度为d的重复度为k/d的一个子串。如果k%d != 0 那么t1.k最多可以不均匀的划分为k/d+1份，最后一个字符为通配符(*)。也可以生成一个长度为d的重复度为k/d的一个子串。 求两个字符串的最短和串，即两个字符串的最短母串，容许发生覆盖。枚举这两个字符串分别作为前缀和后缀的时候形成的和串的长度String s1, s2; 和串无外乎有两种格式：s1s2,s2s1; 但是，中间会发生覆盖。因此，接下来我们就是要计算覆盖部分的长度。假设s1不比s2长，否则，我们交换两个字符串（建议指针实现）考虑三种情况：1. s1的尾覆盖到s2的头，即 2. s2全部覆盖到s1。 即s1包含于s2 3. s1的头覆盖到s2的尾，即 对于第2、3两种情况，用kmp算法在s2中和s1匹配： 如果匹配成功，最终的结果就是s2的长度。 如果匹配失败，则最后匹配的大小就是覆盖的范围a。对于第1种情况，首先可以知道，一定不会匹配成功,，用KMP的思想在s1中部分匹配s2。最后匹配的大小就是覆盖的范围b. 匹配失败之后的最终结果就是len(s1) + len(s2) - max(a, b); Sorce: /showproblem.php?pid=1841 代码见附录二 最长、短公共子串Longest Shortest Common Substring. 析：用KMP算法求最短、长公共子串，没有什么好的方法，就是暴力+枚举的思想。 求n个字符长度最长公共子串。求n个字符长度最长公共子串。对于多模式匹配问题,一般是不可以用KMP解决得，因为忒暴力。思路很简单：我们先按字符串的长度由短到长进行快排。枚举第一个字符串的不同长度子串，判断她是否为下面多有的公共子串？如果是的话，那么我们就表明找到，则比较其长度，如果比已经找到的串长，那么就替换结果串 否则按字典序比较。取字典序考前的，就可以。Sorce：12/JudgeOnline/problem?id=3080 12/JudgeOnline/problem?id=3450 求n个字符长度最长公共子串（带反串的）思路很简单：我们先按字符串的长度由短到长进行快排。枚举第一个字符串的不同长度子串和反子串，判断她们是否为下面多有的公共子串如果是的话，那么我们就表明找到，则比较其长度，如果比已经找到的串长，那么就替换结果串 否则按字典序比较。取字典序考前的，就可以。Sorce：12/JudgeOnline/problem?id=1226 （代码见附录三） 单模式串在主串中匹配的问题。典型的模式匹配问题。这里我们直接用KMP的思想来解决。 一次匹配问题=KMP O(m + n) (m 10)Sorce /faq.php 多次匹配问题：如果我们每次匹配开始的位置为上次匹配成功的位置，那么很可能会超时。因此，这里要进行一点点的优化，我们可以考虑用MP的思想来进行主串匹配：每次匹配成功，主串不回溯，模式串移动到下个位置。（代码见上）Sorce：12/JudgeOnline/problem?id=3461 代码附录四 定义匹配模式匹配问题充分利用KMP的思想进行解决问题。通过一些自定义的匹配原则，进行匹配。这里的关键是找到这个原则。找到这个原则，就当做一般的KMP理解就可以了。（这应该算是KMP算法的一个升级理解）问题概述 告诉一个有1:s(1=s=25)组成的长度为N(1=N=100000)的字符串，找到一个长度为k(1=K= 1; i-) k = i; while (nextk != -1) ret+, k = nextk; if (ret 10007) ret %= 10007; / for_i printf(%dn, ret); / getans sorce: /showproblem.php?pid=3336 问题概述：见算法导论P563。 看不懂英文的看这个。自动机的思想，算导上讲的很清楚，模式串的少的时候用KMP,多的时候用AC自动机或Trie图，其余的不说了！题目简单的说，就是每个节点进行25个字符的匹配，找到他的一个next的指针指向的节点和当前的节点相等。看不懂的，看下面的关键代码吧！是有点不好理解的！void getans() int i, j, p;printf(0 ); for (j = 0; j 25; j+)printf(%d , s0 = tj);printf(%dn, s0 = tj);for (i = 1; i = m; i+) printf(%d , i);for (j = 0; j 25; j+) p = i;while(p != -1 & sp != tj) p = nextp;printf(%d , p+1);/for_jp = i; while(p != -1 & sp != tj) p = nextp;printf(%dn, p+1);/for_i/ getansSorce:浙江理工大学的邀请赛的题目，可以到hoj上去做：link: /showproblem.php?pid=3407 下面这个题目是比较困难的一个，因为要把自动机和DP的思想结合到一起，我DP的思想不咋的。凑合着来吧！ 利用她前缀自动机的思想进行DP要求改变最少的字符使得文本中不含有子串。说是KMP+DP，但是我就是想不到，可能是好久没做字符串的题目了的原因吧，而且这题又是和DP结合到一起的。对我这个大水来说，不可企及了！/设dpij 表示文本串t的后缀1.i-1和模式串的前缀1.j匹配且不出现模式串的状态下删除最小的字符数。/ (1) 在si删除：dpij = dpi-1j+1;/ (2) 在si出匹配，这时要求某个状态s，使T1.s=S1.i-1的后缀，且Ts+1=Si。因此，我们需要知道模式串P的每个位置对应的字符集a.z的状态转移（也就是上次匹配的位置）而且快速实现这也是决定时间复杂度的一个关键地方。由此，我们想到自动机，利用自动机的next指针，快速找到模式串每个位置的状态转移的位置。设trsch表示模式串当前状态s的字母ch的转移。/ dpitrjti = min(dpitrsti, dpij);Link: /showproblem.php?pid=3489 extend-kmp 扩展KMP算法为什么叫做扩展-kmp呢，首先我们看它计算的内容，它是要求出字符串B的后缀与字符串A的最长公共前缀。extendi表示Bi.B_len 与A的最长公共前缀长度，也就是要计算这个数组。 观察这个数组可以知道，kmp可以判断A是否是B的一个子串，并且找到第一个匹配位置？而对于extend数组来说，则可以利用它直接解决匹配问题，只要看extend数组元素是否有一个等于len_A即可。显然这个数组保存了更多更丰富的信息，即B的每个位置与A的匹配长度。 计算这个数组extend也采用了于kmp类似的过程。首先也是需要计算字符串A与自身后缀的最长公共前缀长度。我们设为next数组。当然这里next数组的含义与kmp里的有所过程。但它的计算，也是利用了已经计算出来的next1.i-1来找到nexti的大小，整体的思路是一样的。 具体是这样的：观察下图可以发现 首先在1.i-1,要找到一个k，使得它满足k+nextk-1最大，也就是说，让k加上nextk长度尽量长。 实际上下面的证明过程中就是利用了每次计算后k+nextk始终只增不减，而它很明显有个上界，来证明整个计算过程复杂度是线性的。如下图所示，假设我们已经找到这样的k，然后看怎么计算nexti的值。设len = k+nextk-1(图中我们用Ak代表nextk),分情况讨论： 如果len = i,就是我们在图中表达的情形，这时我们可以看到i这个位置现在等于i-k+1这个位置的元素，这样又分两种情况如果 L = nexti-k+1 = len-i+1,也就是说L处在第二条虚线的位置，这样我们可以看到nexti的大小，至少是len-i+1,然后我们再从此处开始比较后面的还能否匹配，显然如果多比较一次，也会让i+Ai-1多增加1.如果 L len-i+1 也就是说L处在第一条虚线位置，我们知道A与Ak在这个位置匹配，但Ak与Ai-k+1在这个位置不匹配，显然A与与Ai-k+1在这个位置也不会匹配，故nexti的值就是L。 这样nexti的值就被计算出来了，从上面的过程中我们可以看到，nexti要么可以直接由k这个位置计算出来，要么需要在逐个比较，但是如果需要比较，则每次比较会让k+nextk-1的最大值加1.而整个过程中这个值只增不减，而且它有一个很明显的上界k+nextk-1 2*len_A,可见比较的次数要被限制到这个数值之内，因此总的复杂度将是O(N)的。const int maxn = 100;const int maxm = 50;char smaxn, tmaxm;int len_t, nextmaxm;int len_s, extdmaxn;/ p为“作为模式串”的指针，始终指向模式串起始匹配位置（下标）/ q为“作为主串”的指针，始终指向最远匹配的位置，所以每次匹配/ 回溯一个字符; a为“作为主串”的以匹配最远的下标。void get_next(char t, int len_t, int next) int k, a, p, q;next0 = len_t;for (k = 1, q = -1; k len_t; k+, q-) if (q = p) if (q 0) q = 0, p = k;while (p len_t & tp = tq) p+, q+;nextk = q; a = k; else nextk = nextk-a; /for_for (k = 0; k len_t; k+) printf(next%d = %dn, k, nextk); /get_nextvoid get_extd(char s, int len_s, char t, int len_t) get_next(t, len_t, next);int k, a, p, q;for (k = 0, q = -1; k len_s; k+, q-) if (q = p) if (q 0) q = 0, p = k;while (p len_s & q len_t & sp = tq) p+, q+;extdk = q; a = k; else extdk = nextk - a; /for_kfor (k = 0; k len_s; k+) printf(extd%d = %dn, k, extdk); / get_extd; ExtendKmp的应用： 求一个串的最长回文串的长度 令所给字符串为a，则找到中点mid位置，一后半段做为模式串，把a倒过来生成b，求出b串在该模式串的每一位的next1i;在以字符串a的前半段的逆串作为模式串，求出a串在该模式串下的next2。然后遍历a串的每一位，根据next1和next2就可以判断此处是否回文，但这个回文只能判断跨越中点mid的回文，因此这里要进行划分递归，分别在a的前半段和后半段重复此算法即可找到最大回文串。Hdu 3068_ /showproblem.php?pid=3068 Trie树Trie树 又称单词查找树，字典树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。Trie树性质 它有3个基本性质：1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。2. 每个节点对应一个路径字符串。3. 每个节点的所有子节点包含的字符都不相同。基本操作 查找，插入，删除， 搜索。查找一个字符串时，我们只需从根结点按字符串中字符出现顺序依次往下走。如果到最后字符串结束时(即到达叶子节点)，对应的结点标记为红色，则该字符串存在;否则不存在（即找到该字符串，但是没到达叶子节点，或者找不到该字符串，两种情况考虑可以归结为一种情况，即没有到达叶子节点）。插入时也只需从根结点往下遍历，碰到已存在的字符结点就往下遍历，否则，建立新结点;最后标记最后一个字符的结点（叶节点）为红色即可。删除的操作，删除一个字符串的时候，我们只要先找到该字符串所在的叶子结点，然后把该节点设为“空”，然后在向他的父节点遍历，知道某个节点存在分支或者是根节点。Trie树的基本结构：trie树的问题，比较简单。实际上trie树作为一种基本的数据结构，在后面的高级的数据结构里面是经常用到的，这里只是简单的提一下。const int maxc = 26;const int maxs = 100000;struct node int flg, nextmaxc; void set() flg = 0; memset(next, -1, sizeof(next); void out() printf(flg = %dn, flg); for (int i = 0; i maxc; i+) printf(%d , nexti); puts(); tmaxs;int nod;inline int id(char c) return c-a;void insert(char *s) int p = 0, i = -1, d; while(s+i) d = id(char c); if(tp.nextd = -1) t+nod.set(); tp.nextd = nod; tp.flg+;Trie树的应用Pku_1056_ IMMEDIATE DECODABILITY 12/JudgeOnline/problem?id=1056 Pku_1451_T9 12/JudgeOnline/problem?id=1451 PKU_2001_shortest_Prext: 给定N(1 N = 1000)个有小写字母组成的长度小于20字符串. 要求给出能唯一代表每个字符串的最小前缀。 Root: 由于数据量的限制，这里我们考虑字典树的解法，分析字典树的特点： 最小不重复前缀：定义为一代表一个字符串的最小前缀。 我们可以得到，一个字符串的最小不重复前缀为下列两种情况： 1. 如果该表示字符串的路径上，已经到达叶节点， 并且该节点之下还有孩子。 那么最小不重复前缀就为该字符串本身。2. 否则，在查找的路径上，如果遇到一个字节点，只有一个字符串覆盖掉他, 那么，足校不重复前缀就为这个串到这个字符为止的子字符串。【代码见附录六】 link: 12/JudgeOnline/problem?id=2001 Pku_2503_BabelFish 12/JudgeOnline/problem?id=2503 PKU_3630_Phone_List 12/JudgeOnline/problem?id=3630 pku_3690_Constellations (注意降维：二维变一维)AC自动机ac自动机 以看成是kmp在多字符串情况下扩展形式，可以用来处理多模式串匹配。只要为这些模式串建立一个trie树，然后再为每个节点建立一个失败指针，也就是类似与kmp的next函数，让我们知道如果匹配失败，可以再从哪个位置重新开始匹配。ac实际上两个人的名字的首字母，Aho-Corasick。 应该还记得，在kmp构造next数组时，我们是从前往后构造，即先构造1.i-1，然后再利用它们计算nexti,这里也是类似。不过这个先后，是通过bfs的顺序来体现的。AC自动机的失败指针具有同样的功能，也就是说当我们的模式串在Tire上进行匹配时，如果与当前节点的关键字不能继续匹配的时候，就应该去当前节点的失败指针所指向的节点继续进行匹配。而从根到这个失败指针指向的节点组成的字符串，实际上就是跟当前节点的后缀的匹配最长的字符串。 AC 自动机是在Trie树的基础上变换而来的，这里可以快速解决多模式的匹配问题。其中flg用来标记那些该节点覆盖的字符串const int maxc = 4;const int maxn = 520;const int maxs = 20020;struct node int flg, suf, nextmaxc; void set() flg = suf = 0; memset(next, -1, sizeof(next); void out() printf(flg=%d,suf=%dn,flg,suf); for (int i = 0; i 4; i+) printf(%d , nexti); puts(); tmaxn;/ 把字符串s插入到trie树int nod;inline int id(char c) return c-a;void insert(char *s) int p = 0, i = -1, d; while(s+i) d = id(char c); if(tp.nextd = -1) t+nod.set(); tp.nextd = nod; tp.flg+;/* AC自动机和KMP算法的next函数具有相似的作用，是说，当我们的模式串在Tire上进行匹配是，如果与当前节点的关键字不能继续匹配的时候，就应该去当前节点的失败指针所指向的节点继续匹配。构造失败指针的过程：设当前节点的字母为C, 则继续沿着他父节点的失败指针走，直到走到一个节点，他的儿子中也有字母为C的节点。然后把当前节点的失败指针指向那个字母也为C的儿子。如果一直走到了root都没找到，那就把失败指针指向root。具体的操作起来就是：先把root加入队列（root的失败指针指向自己或者NULL），这以后我们每处理一个节点，就把它的所有儿子加入队列，队列为空为结束的标志。*/ void ac() int i, p; he