kmp,trie,AC全面解析

余姚中学罗方炜1Kmp_trie_AC自动机余姚中学罗方炜[e-mail]余姚中学罗方炜2kmp什么是子串：对于一个字符串变量，例如“adereegfbw”,它的子串就是像“ader”这样可以从中找到的连续的字符串。字符串“adereegfbw”本身也属于它本身最长的子串。子串计算方法：ab的子串：a、b、ab共3个即（2+1）个，abc的子串：a、b、c、ab、bc、abc共（3+2+1）个，所以若字符串的长度为n,则子串的个数就是[n+(n-1)+.......+1]个，software中非空子串的个数就是8+7+....+1=36个，如果包括空串,则应为37个。余姚中学罗方炜3kmp串的模式匹配：令s为主串，t为模式串(1..n,1..m)当匹配不成功的时候，我们希望主串在匹配的时候不回溯，而模式串能迅速的回溯到该重新匹配的地方当s[i]!=t[j]时，对于之前的j-1个字符，有:s[i-j+1]s[i-j+2]..s[i-1]=t[1][t2]..t[j-1](1)余姚中学罗方炜4Kmp那么，我们希望j回溯到k位置，能使得：s[i-k+1]s[i-k+2]..s[i-1]=t[1]t[2]..t[k-1](kj)(2)根据(1)，我们得出:s[i-k+1]s[i-k+2]..s[i-1]=t[j-k+1]t[j-k+2]..t[j-1](kj)(3)由(2),(3)得：t[1]t[2]..t[k-1]=t[j-k+1]t[j-k+2]..t[j-1](kj)(4)余姚中学罗方炜5kmp由此，串的模式匹配重点构造模式串t构造回溯的next数组，用于记录匹配失败后模式串回溯的位置为了加速找next数组，可以采用压缩路径的方式next[i]=next[j](具体写法要根据题目需求)余姚中学罗方炜6kmpvoidgetNext(){next[0]=-1;//next数组0-n,包括nfor(inti=0,j=-1;in;){if(j==-1||str[i]==str[j]){i++,j++;if(str[i]==str[j])next[i]=next[j];//一样的字符，如果要回溯，就递归回溯elsenext[i]=j;//不然就回溯到j,意味着前j个一样}elsej=next[j];}}余姚中学罗方炜7kmpkmp相关题目Hdu2087Hdu1358(next数组应用)任务：每人推荐一道。。。余姚中学罗方炜8trieTrie树(单词查找树，字典树)余姚中学罗方炜9trie//结点数组写法constintdig=26;constintM=500001;#defineroot0;structnode{intcnt,sun[dig];//网上很多指针写法，省空间voidinit(){cnt=0;for(inti=0;idig;i++)sun[i]=-1;}}p[M];inttot;余姚中学罗方炜10trievoidinsert(char*s){//建字典树intj=root;for(inti=0;s[i];i++){intk=s[i]-'a';if(p[j].sun[k]==-1){p[tot].init();p[j].sun[k]=tot++;}j=p[j].sun[k];p[j].cnt++;//根据情况设计cnt}}余姚中学罗方炜11trietrie相关题目Hdu1251Pku1204(题意：给定一个字符矩阵，然后给你一些字符串，让你在矩阵里找出这个字符串，如果存在，输出第一个字符位置以及方向(A-H从北开始顺时针八个方向))=27276#overview解法：对字符串构造trie树，然后枚举矩阵里每个点及八个方向，走一趟trie树，判断是否在trie上有cnt余姚中学罗方炜12AC自动机AC自动机可以说是kmp与trie树的结合利用trie树的树形结构，在trie树上构造类似next的fail指针，表示匹配失败后回溯到树的哪个位置Trie树就相当于模式串余姚中学罗方炜13AC自动机余姚中学罗方炜14AC自动机余姚中学罗方炜15AC自动机KMP算法是单模式串的字符匹配算法，AC自动机是多模式串的字符匹配算法。AC自动机的构造：1.构造一棵Trie，作为AC自动机的搜索数据结构。2.构造fail指针，使当前字符失配时跳转到具有最长公共前缀的字符继续匹配。如同KMP算法一样，AC自动机在匹配时如果当前字符匹配失败，那么利用fail指针进行跳转。由此可知如果跳转，跳转后的串的前缀，必为跳转前的模式串的后缀并且跳转的新位置的深度（匹配字符个数）一定小于跳之前的节点。所以我们可以利用bfs在Trie上面进行fail指针的求解。3.扫描主串进行匹配。余姚中学罗方炜16AC自动机构造失败指针的过程概括起来就一句话：设这个节点上的字母为C，沿着他父亲的失败指针走，直到走到一个节点，他的儿子中也有字母为C的节点。然后把当前节点的失败指针指向那个字母也为C的儿子。如果一直走到了root都没找到，那就把失败指针指向root。具体操作起来只需要：先把root加入队列(root的失败指针指向自己或者NULL)，这以后我们每处理一个点，就把它的所有儿子加入队列，队列为空。余姚中学罗方炜17AC自动机structnode{intfail,cnt,sun[dig];//intdg;//dg方便调试，显示出节点是什么字符voidinit(){fail=0,cnt=0;//dg=-1;for(inti=0;idig;i++)sun[i]=-1;}}p[M];//结点中增加fail数据余姚中学罗方炜18AC自动机余姚中学罗方炜19AC自动机匹配过程分两种情况：(1)当前字符匹配，表示从当前节点沿着树边有一条路径可以到达目标字符，此时只需沿该路径走向下一个节点继续匹配即可，目标字符串指针移向下个字符继续匹配；(2)当前字符不匹配，则去当前节点失败指针所指向的字符继续匹配，匹配过程随着指针指向root结束。重复这2个过程中的任意一个，直到模式串走到结尾为止。余姚中学罗方炜20AC自动机余姚中学罗方炜21AC自动机AC自动机相关题目Hdu2222裸题Poj2778(题意：由A,C,T,G组成的长度为n的字符串里，不包含给定的m个字符串有几种。解法：AC自动机+快速幂矩阵乘法)余姚中学罗方炜22AC自动机余姚中学罗方炜23AC自动机余姚中学罗方炜24AC自动机矩阵的构造：根据trie树的指针，a[i][j]表示i字符后接j字符是否合法，如果合法就数量增加矩阵乘法的意义：i直达j的路径数，那么矩阵自乘n次，就是从i开始，经过n个点到达j的路径种类数余姚中学罗方炜25AC自动机最后统计到达不含cnt的j点的总数余姚中学罗方炜26AC自动机Poj3691题意:给定N个模式串(1≤N≤50)最大长度为20一个主串(长最大为1000)允许涉及的字符为4个{'A','T','G','C'}求最少修改几个字符使主串不包含所有模式串余姚中学罗方炜27AC自动机解法：AC自动机-有限状态自动机(DFA)-有向图的动态规划余姚中学罗方炜28AC自动机构造trie图与poj2778类似，每个点都有可能被构造，所以需要在trie图中都有相应的状态。如果每个点的i儿子在字典树上没有这个结点，把指向它fail位置的i儿子如果还是没有就指向root(当前点就是root特判)余姚中学罗方炜29AC自动机在保证每个点的儿子都存在前提下，fail指针就比较好构造了原来的方法：设这个节点上的字母为C，沿着他父亲的失败指针走，直到走到一个节点，他的儿子中也有字母为C的节点。然后把当前节点的失败指针指向那个字母也为C的儿子。如果一直走到了root都没找到，那就把失败指针指向root。现在的方法：设这个结点上的字母为C，将它指到它父亲失败指针的C儿子位置。(因为每个结点所有儿子都构造好了)余姚中学罗方炜30AC自动机构造fail指针的时候，别忘了对cnt也构造如果某个点的cnt=1，那么fail指向它的位置上的点cnt也要等于1，意义就是也被标记(病毒感染)了，如右图：余姚中学罗方炜31AC自动机构造好trie图之后，我们就可以DP了dp状态：dp[i][j]表示到第i个字符串时，达到状态j不经过危险节点的最小耗费。dp转移：dp[i][j.child[k]]=min(dp[i][j.child[k]],dp[i-1][j]+(k!=ch(str[i])));余姚中学罗方炜32AC自动机以样例中2ATGTGAATG为例余姚中学罗方炜33AC自动机第一个字符可以保留为T，代价为0，也可以变G,C，代价为1，而A都是不允许的之后G，C可以任意转移到G,C,T，但T不能转移到G，只能转移到C,T，转移的时候，如果字符和当前本串的字符相同，代价不用增加，否则+1，最后的结果就是取合法状态中，最小的代价余姚中学罗方炜34AC自动机余姚中学罗方炜35AC自动机总结：AC自动机的应用中，字符串的匹配是其最原始的功能构造trie图，然后在trie图上根据状态的合法性构造合法字符串是比较常见的模型余姚中学罗方炜36AC自动机继续推荐题：Poj1625Hdu3341Hdu4117余姚中学罗方炜37谢谢！