首页 > 代码库 > 学渣乱搞系列之扩展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 }
View Code