KMP算法AC自动机.ppt

KMP算法 AC自动机 By Cajon Pass 字符串匹配 字符串匹配中的几个概念 模式串：等待被在主串中匹配的串 主串：被模式串匹配的串 字符串匹配：在主串中查找模式串的过程 比如对于主串: aabbcc 与模式串：aa 来说，一般所要进行的匹配是在主串中查找模式串第一次出现的位置，比如模式串：aa 在主串：aabbcc 中第一次出现的位置是1。 字符串匹配的暴力算法 暴力算法的实现 设i指针为主串s第i位置的字符，j指针为模式串p第j位置的字符，最开始i与j均从0开始，当s[i]==p[j]时,i++,j++，主串与模式串开始比较下一位。当s[i]!=p[j]时，j设为0，i设为上一次s[i]==p[j]时i的值加1，即将模式串往后滑动一位，并且模式串与主串的匹配再次从模式串的第0个字符开始,若有哪些信誉好的足球投注网站到模式串即记录下来，若未有哪些信誉好的足球投注网站到模式串，将会在i指针到达主串s末尾时结束程序。 很显然时间复杂度为O(nm) 代码: KMP算法 概述 KMP算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。 KMP算法 如何让模式匹配加速 s串:abcdddabcdddabcdddabcdddabcdddaa p串:abcdddabcdddabcdddaa 求p串在s串中第一次出现的位置 第一次匹配： s:abcdddabcdddabcdddabcdddabcdddaap:abcdddabcdddabcdddaa 在蓝色字符处失配，按照暴力算法，我们应该将p串右移一位，从p串的第一个字符开始重新与s串比较,但是我们可以发现，我们并不需要这样比较。 我们可以发现，事实上，p串的绿色与红色部分和红色与橙色部分是相同的，也就是说，对于绿色与红色部分的任意一段字符，它在主串中下一次出现的位置必然是是红色与橙色部分中与之对应的那段字符的位置。 比如说abcddda在主串中下一次出现的位置必然是abcddda 同理abcdddabcddda下一次出现的位置必然是abcdddabcddda 所以我们在进行下一次匹配的时候直接将abcdddabcdddab中的b与失配的那个b继续对比即可，不再需要做无谓的重复计算，而如果失配的位置不在模式串尾部，我们也可以通过当前位置之前字符串的头与尾的相同字符段位置计算出下一次比较的位置。 而如何记录到每一个位置时之前相同的字符段的位置，或是说最大长度（因为必然从头开始，位置与最大长度是同一个值）呢？这时候就需要喜闻乐见的next数组了。 NEXT数组 关于NEXT数组 有了上面的铺垫，我们就可以知道next数组的作用了，它的作用就是记录字符串每一个位置之前的子字符串中头部与尾部相同的字符段的最大长度，换句话说，就是记录到当前位置（不包括当前字符）之前的那一段子字符串头与尾中相同的字符段的最长长度。 如字符串 agctagcagctagctg 的next数组值就为 -1 0 0 0 0 1 2 3 1 2 3 4 5 6 3 4 NEXT数组 如何求解NEXT数组？ 现在我们面临着一个实际的问题：如何求一段字符串的NEXT数组值。 其实很简单 对于字符串 agctagcagctagctg 来说 我们指定两个指针i,j。i指定当前求解的next值的位置，j为以i位置前一个字符为尾的子字符串中的next值，换句话说就是以i位置前一个字符为尾的子字符串中头与尾匹配的头部所能到达的最大位置。最开始时i=1,j=0。 现在开始讨论几种情况： 当j==-1时，代表已经找不到长度大于1的字符串循环了，此时就可以将i位置的next值设为0，然后i++,j++,如果存在长度等于1的字符串循环的话，在下一次判断时i+1的值就会为1（这是正确的，因为关于i的next值是i之前（不包括i）的子字符串的最大循环长度） 当t[i]==t[j]时,说明延续了前一个子字符串的对称性，i++,j++,并将next[i]=j，这样子就可以将当前位置为尾(i)的next值赋值进下一个位置(i+1)，并且下一次判断也就从(i+1)这个位置开始了。 当t[i]!=t[j]且j!=-1时，说明不可能延续前一个子字符串的对称性，也不一定不存在更小的字符串循环，此时将j=next[j]，它的意思就是在当前的对称中继续寻找子对称（因为如果t[i]是某个更小的字符串循环的最后一个字符，那么为了保证它前方字符同样存在对称性，以t[i]为尾的更小的字符串循环必然在当前已经存在的t[