首页 > 代码库 > 学渣乱搞系列之扩展KMP的那点事
学渣乱搞系列之扩展KMP的那点事
扩展KMP牵涉了一些相对运动的姿势,比较费解!本学渣看了一天的扩展KMP,打算写点东西。。。本文看后,出现的后果本人一概不负责。毕竟我不是很会表达。
扩展KMP是搞什么灰机的?本学渣所知道的扩展KMP是来解集训篇那道字符串题的。有了犯罪动机,现在就要下手。不要以为扩展KMP就以为与KMP关系暧昧。屁大点事,两个根本不是一个东西。只是有点思想是一致的,就是利用已经匹配的信息避免一些不必要的匹配。
以此提高匹配速度。不过扩展KMP也能干KMP干的事。但是速度没KMP那么快。
扩展KMP要造两个数组,一个Next数组,一个exd数组,前一个是存储模式串的后缀串的最长前缀长,exd数组就是我们的终极目标!我们的终极目标是干吗?泡妞把妹?AC?。。。。。。
后缀造了造前缀?下面讲下如何求next吧,网上很多教程都是讲求exd的。假设s就是串t。
Exd[i] = s[i….n]与t[1..m]的最大前缀长度。(i > = 0 && I < n)
假设s[a…p] == t[0..p-a]表示a位置与模式串所能达到的最大前缀长度。
那么我们有a <= k <= p 且 s[k…p] == t[k-a…p-a]
为什么啊?相对位置啊k – a = x – 0; x = k-a;
现在假设我们要求next[i]。 i > k ;
还记得我们上一次匹配吗??那时候的s[a]是与t[0]对齐。现在我们利用的就是这次对齐。
求next[i]就是要把t[0]与s[i]对齐。那么next[i-a]存的是什么呢?是不是s[a]与t[0]对齐时,
S[i]是不是与t[i-a]对齐的呢?I – a = x – 0 ; x = i-a;
那么从next[i-a]记录的是什么东西呢?是不是表示t[i-a]与t[0]对齐时的最长前缀么?
假设L = next[i-a];
求的是next[i] 此时是把s[i]与t[0]对齐,前面有t[i-a]与t[0]的最大前缀,t[i-a]又正是上次对着s[i]的,所以L很有可能就是s[i]与t[0]对齐时的最长前缀。为什么是很有可能呢?
设p = a + next[a]-1; 上次的匹配范围是多少来着?s[a,p] == t[0,p-a] 匹配i时,i+L-1很有可能超过p,超过的世界,那是我们没有匹配过的。所以要单独处理下。
而i+L-1 < p 则一切尽在匹配之中,exd[i]就等于L,没有等于啊。。。。因为无法确定后面的是不是失配了。。。
为什么不能再长呢?因为因为,t[i-a…p-a]只有L长的与t[0…p-a]匹配啊。。。
为什么求出next[i],因为next[a]已经求出了,i-a<= i 求next[i]时,next[i-a]早已求出。。。。。
好了,现在大家终于都不理解啥是扩展KMP了。欢迎各种乱评。。。
show me your code?
1 int next[200]; 2 char p[] = "aaaa"; 3 void getNext(){ 4 int i,k = 1; 5 for(i = 0; p[i+1] && p[i] == p[i+1]; i++);//暴力解决 6 next[1] = i; 7 for(i = 2; p[i]; i++){ 8 int t = k+next[k],j = i+next[i-k]; 9 if(j < t) next[i] = j;10 else{11 for(j = t-i; p[i+j] && p[i] == p[i+j]; j++);12 next[k = i] = j;13 }14 }15 }