KMP算法，想必大家都不陌生，它是求串匹配問(wèn)題的一個(gè)經(jīng)典算法（當(dāng)然如果你要理解成放電影的KMP，請(qǐng)退出本頁(yè)面直接登錄各大電影網(wǎng)站，謝謝），我想很多人對(duì)它的理解僅限于此，知道KMP能經(jīng)過(guò)預(yù)處理然后實(shí)現(xiàn)O(N*M）的效率，比brute force（暴力算法）更優(yōu)秀等等，其實(shí)KMP算法中的Next函數(shù)，功能十分強(qiáng)大，其能力絕對(duì)不僅僅限于模式串匹配，它并不是KMP的附屬品,其實(shí)它還有更多不為人知的神秘功能^_^
先來(lái)看一個(gè)Next函數(shù)的典型應(yīng)用，也就是模式串匹配，這個(gè)相信大家都很熟悉了:
POJ 3461 Oulipo——很典型的模式串匹配問(wèn)題，求模式串在目標(biāo)串中出現(xiàn)的次數(shù)。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 1000001
char t[MAX];
char s[MAX];
int next[MAX];
inline void calnext(char s[],int next[])
{
int i;
int j;
int len=strlen(s);
next[0]=-1;
j=-1;
for(i=1;i<len;i++)
{
while(j>=0&&s[i]!=s[j+1])
j=next[j];
if(s[j+1]==s[i])//上一個(gè)循環(huán)可能因?yàn)閖=-1而不做，此時(shí)不能知道s[i]與s[j+1]的關(guān)系。故此需要此條件。
j++;
next[i]=j;
}
}
int KMP(char t[],char s[])
{
int ans=0;
int lent=strlen(t);
int lens=strlen(s);
if(lent<lens)
return 0;
int i,j;
j=-1;
for(i=0;i<lent;i++)
{
while(j>=0&&s[j+1]!=t[i])
j=next[j];
if(s[j+1]==t[i])
j++;
if(j==lens-1)
{
ans++;
j=next[j];
}
}
return ans;
}
int main()
{
int testcase;
scanf("%d",&testcase);
int i;
for(i=1;i<=testcase;i++)
{
scanf("%s%s",s,t);
calnext(s,next);
printf("%d\n",KMP(t,s));
}
return 0;
}——————————————————————————————————————————————————————————————————————————————————————
POJ 2406 Power Strings
這道題就比較有意思了，乍看之下，怎么看貌似都與KMP無(wú)關(guān)，呵呵，這就是因?yàn)槟銢](méi)有深入理解Next 的含義；
我首先來(lái)解釋下這道題的題意，給你一個(gè)長(zhǎng)度為n的字符串，首先我們找到這樣一個(gè)字符串，這個(gè)字符串滿(mǎn)足長(zhǎng)度為n的字符串是由這個(gè)字符串重復(fù)疊加得到并且這個(gè)字符串的長(zhǎng)度要最小.，然后輸出重復(fù)的次數(shù)。
比如說(shuō)，ababab這個(gè)字符串，顯然它是由ab重復(fù)疊加3次得到，所以，答案輸出3.
那么這個(gè)題用next怎么做呢，我們必須知道，next數(shù)組里面存放的是 如果當(dāng)前匹配失敗，模式串可以繼續(xù)進(jìn)行匹配的下一個(gè)位置。
For Example:
1 2 3 4 5 6
S= a b a b a ？
Next= 0 0 1 2 3 ？
其中next[5]=3,說(shuō)明如果模式串在j=6處匹配失敗，那么j=next[5]=3 ，為什么? 因?yàn)镾的頭三位和末三位是一樣的，如果說(shuō)S已經(jīng)匹配到5的位置（匹配到5說(shuō)明前5位都已經(jīng)匹配上），那么前三位肯定也匹配上了（廢話(huà)~），若果這個(gè)時(shí)候要繼續(xù)匹配，我們可以將模式串向右平移幾個(gè)個(gè)單位，這樣保證S的前三位仍然是可以匹配上的。
比如說(shuō)目標(biāo)串是
i= 1 2 3 4 5 6 7 8 9
a b a b a
d e f g
a b a b a
c
j= 1 2 3 4 5 6
next= 0 0 1 2 3 ?
現(xiàn)在我們發(fā)現(xiàn)i=6與j=6兩串不匹配怎么辦?由于next[5]指向3,那么我們將模式串平移
i= 1 2 3 4 5 6 7 8 9
a b a b a d e f g
a b a b a c
j= 1 2 3 4 5 6
next= 0 0 1 2 3 ?
這樣我們從j=3處繼續(xù)向后匹配。（當(dāng)然如果此時(shí)i=6與j=4仍然不匹配，那么我們繼續(xù)使用失敗函數(shù)，去尋找下一個(gè)位置）
好的，現(xiàn)在我們已經(jīng)知道了，next數(shù)組中所存放的數(shù)字的含義，那么接下來(lái)讓我們來(lái)看看怎樣靈活的使用next,揭開(kāi)它不為人知的另一面吧。
回到原題，原題要求求出一個(gè)字符串的某一個(gè)子串，使得這個(gè)字符串不斷自我疊加后得到原串，并且這個(gè)重復(fù)的次數(shù)最多。那么它和next有什么關(guān)系呢？？？
結(jié)論：如果有一個(gè)字符串s,長(zhǎng)度是len,它的失敗函數(shù)是next，如果len能被len-next[len]整除，那么len-next[len]就是我們要求的那個(gè)子串的長(zhǎng)度，與之對(duì)應(yīng)的字符串，就是我們想得到的子串；
為什么呢？ 假設(shè)我們有一個(gè)字符串a(chǎn)babab,那么next[6]=4對(duì)吧，由于next的性質(zhì)是，匹配失敗后，下一個(gè)能繼續(xù)進(jìn)行匹配的位置，也就是說(shuō)，把字符串的前四個(gè)字母，abab,平移2個(gè)單位，這個(gè)abab一定與原串的abab重合（否則就不滿(mǎn)足失敗函數(shù)的性質(zhì)），這說(shuō)明了什么呢，由于字符串進(jìn)行了整體平移，而平移后又要重疊，那么必有
s[1]=s[3],s[2]=s[4],s[3]=s[5],s[4]=s[6].說(shuō)明長(zhǎng)度為2的字符串在原串中一定重復(fù)出現(xiàn)，這就是len-next[len]的含義！
解決上面這個(gè)問(wèn)題的同時(shí)，其實(shí)還有另一個(gè)問(wèn)題，那就是如果這個(gè)字符串長(zhǎng)度為奇數(shù)怎么辦？如ababa,好像next[len]也等于3呢，可是aba-ba-似乎并不是由ba重復(fù)得到的吧。我們先把這個(gè)字符串?dāng)嚅_(kāi)，ab-ab-a，可以想象，中間的ab平移后，沒(méi)有ab與它重合(只能重合一個(gè)，這雖然沒(méi)有違背next的性質(zhì)，但是卻對(duì)本題的方法造成了影響，請(qǐng)讀者細(xì)細(xì)品味），所以才會(huì)出現(xiàn)上面的情況！所以要加上len能夠整除len-next[len]這個(gè)條件.
此題源代碼如下:
//This is the source code for POJ 2406
//coded by abilitytao
//2009年7月31日11:17:34
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 1000001
int next[MAX];
inline void calnext(char s[],int next[])
{
int i;
int j;
int len=strlen(s);
next[0]=-1;
j=-1;
for(i=1;i<len;i++)
{
while(j>=0&&s[i]!=s[j+1])
j=next[j];
if(s[j+1]==s[i])
j++;
next[i]=j;
}
}
int main()
{
int n;
char str[MAX];
int len;
while(scanf("%s",&str))
{
if(str[0]=='.')
break;
len=strlen(str);
calnext(str,next);
if((len)%(len-1-next[len-1])==0)
printf("%d\n",(len)/(len-1-next[len-1]));
else
{
putchar('1');
putchar('\n');
}
}
return 0;
}
POJ 1961與上題類(lèi)似，故不贅述，代碼如下：
//This is the source code for POJ 1961
//coded by abilitytao
//2009年7月31日10:56:07
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 1000001
int next[MAX];
void calnext(char s[],int next[])
{
int i;
int j;
int len=strlen(s);
next[0]=-1;
j=-1;
for(i=1;i<len;i++)
{
while(j>=0&&s[i]!=s[j+1])
j=next[j];
if(s[j+1]==s[i])
j++;
next[i]=j;
}
}
int main()
{
int n;
char str[MAX];
int casenum=0;
int i;
int len;
while(scanf("%d",&n))
{
casenum++;
if(n==0)
break;
scanf("%s",str);
len=strlen(str);
printf("Test case #%d\n",casenum);
calnext(str,next);
for(i=1;i<len;i++)
{
if((i+1)%(i-next[i])==0&&next[i]!=-1)
printf("%d %d\n",i+1,(i+1)/(i-next[i]));
}
printf("\n");
}
return 0;
}
POJ 2752 Seek the Name, Seek the Fame
這道題揭開(kāi)了next的另一個(gè)應(yīng)用^_^
題目的意思可以這樣描述：給出一個(gè)字符串S,長(zhǎng)度為len;找出一個(gè)前綴一個(gè)后綴，使得這兩個(gè)字符串相同。 輸出所有可能的情況。
如aaaaa,
aaaaa ——》OK
aaaaa ——》OK
aaaaa + aaaaa ——》OK
aaaaa + aaaaa ——》OK
aaaaa + aaaaa ——》OK
那么這個(gè)題怎么用next呢，其實(shí)很簡(jiǎn)單，只要你知道next的含義。 s[1]——s[next[len]]中的內(nèi)容一定能與s[1+len-next[len]]——s[len]匹配，所以s[1]——s[next[len]]就是我們要求取的最長(zhǎng)的那個(gè)串，然后呢我們循環(huán)地利用next,由于next的性質(zhì)，可以保證，每一次得出的字串都能匹配到最后一個(gè)字母，也就是得到一個(gè)前綴等于后綴。只不過(guò)這個(gè)字符串的長(zhǎng)度在不斷地減小罷了。不斷地使用next我們直到求出所有的前綴^_^ So the problem is cleared.
附源代碼:
//This is the source code for POJ 2752
//coded by abilitytao
//2009年7月31日12:17:45
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 1000001
int next[MAX];
inline void calnext(char s[],int next[])
{
int i;
int j;
int len=strlen(s);
next[0]=-1;
j=-1;
for(i=1;i<len;i++)
{
while(j>=0&&s[i]!=s[j+1])
j=next[j];
if(s[j+1]==s[i])//上一個(gè)循環(huán)可能因?yàn)閖=-1而不做，此時(shí)不能知道s[i]與s[j+1]的關(guān)系。故此需要此條件。
j++;
next[i]=j;
}
}
int record[MAX];
int main()
{
char str[MAX];
int len;
int p=0;
int j;
while(scanf("%s",&str)!=EOF)
{
calnext(str,next);
p=0;
len=strlen(str);
j=len-1;
while(j!=-1)
{
record[++p]=j;
j=next[j];
}
while(p>1)
{
printf("%d ",record[p]+1);
p--;
}
printf("%d\n",record[p]+1);
}
return 0;
}
文章寫(xiě)完了，如果有什么疏漏，還請(qǐng)大家批評(píng)指正~
文章來(lái)自abilitytao博客
轉(zhuǎn)載請(qǐng)注明出處：
http://m.shnenglu.com/abilitytao/archive/2009/08/01/91865.html