深度剖析KMP,讓你認識真正的Next

KMP算法，想必大家都不陌生，它是求串匹配問題的一個經典算法（當然如果你要理解成放電影的KMP，請退出本頁面直接登錄各大電影網站，謝謝），我想很多人對它的理解僅限于此，知道KMP能經過預處理然后實現O(N*M）的效率，比brute force（暴力算法）更優秀等等，其實KMP算法中的Next函數，功能十分強大，其能力絕對不僅僅限于模式串匹配，它并不是KMP的附屬品,其實它還有更多不為人知的神秘功能^_^

先來看一個Next函數的典型應用，也就是模式串匹配，這個相信大家都很熟悉了:
POJ 3461 Oulipo——很典型的模式串匹配問題，求模式串在目標串中出現的次數。

——————————————————————————————————————————————————————————————————————————————————————
POJ 2406 Power Strings
這道題就比較有意思了，乍看之下，怎么看貌似都與KMP無關，呵呵，這就是因為你沒有深入理解Next 的含義；
我首先來解釋下這道題的題意，給你一個長度為n的字符串，首先我們找到這樣一個字符串，這個字符串滿足長度為n的字符串是由這個字符串重復疊加得到并且這個字符串的長度要最小.，然后輸出重復的次數。
比如說，ababab這個字符串，顯然它是由ab重復疊加3次得到，所以，答案輸出3.

那么這個題用next怎么做呢，我們必須知道，next數組里面存放的是 如果當前匹配失敗，模式串可以繼續進行匹配的下一個位置。
For Example:
        1 2 3 4 5 6
     S= a b a b a ？
  Next= 0 0 1 2 3 ？
其中next[5]=3,說明如果模式串在j=6處匹配失敗，那么j=next[5]=3 ，為什么? 因為S的頭三位和末三位是一樣的，如果說S已經匹配到5的位置（匹配到5說明前5位都已經匹配上），那么前三位肯定也匹配上了（廢話~），若果這個時候要繼續匹配，我們可以將模式串向右平移幾個個單位，這樣保證S的前三位仍然是可以匹配上的。

比如說目標串是

    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  ? 
現在我們發現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處繼續向后匹配。（當然如果此時i=6與j=4仍然不匹配，那么我們繼續使用失敗函數，去尋找下一個位置）

 好的，現在我們已經知道了，next數組中所存放的數字的含義，那么接下來讓我們來看看怎樣靈活的使用next,揭開它不為人知的另一面吧。
回到原題，原題要求求出一個字符串的某一個子串，使得這個字符串不斷自我疊加后得到原串，并且這個重復的次數最多。那么它和next有什么關系呢？？？

結論：如果有一個字符串s,長度是len,它的失敗函數是next，如果len能被len-next[len]整除，那么len-next[len]就是我們要求的那個子串的長度，與之對應的字符串，就是我們想得到的子串；

為什么呢？ 假設我們有一個字符串ababab,那么next[6]=4對吧，由于next的性質是，匹配失敗后，下一個能繼續進行匹配的位置，也就是說，把字符串的前四個字母，abab,平移2個單位，這個abab一定與原串的abab重合（否則就不滿足失敗函數的性質），這說明了什么呢，由于字符串進行了整體平移，而平移后又要重疊，那么必有
s[1]=s[3],s[2]=s[4],s[3]=s[5],s[4]=s[6].說明長度為2的字符串在原串中一定重復出現，這就是len-next[len]的含義！
解決上面這個問題的同時，其實還有另一個問題，那就是如果這個字符串長度為奇數怎么辦？如ababa,好像next[len]也等于3呢，可是aba-ba-似乎并不是由ba重復得到的吧。我們先把這個字符串斷開，ab-ab-a，可以想象，中間的ab平移后，沒有ab與它重合(只能重合一個，這雖然沒有違背next的性質，但是卻對本題的方法造成了影響，請讀者細細品味），所以才會出現上面的情況！所以要加上len能夠整除len-next[len]這個條件.

此題源代碼如下:


POJ 1961與上題類似，故不贅述，代碼如下：

POJ 2752 Seek the Name, Seek the Fame
這道題揭開了next的另一個應用^_^
題目的意思可以這樣描述：給出一個字符串S,長度為len;找出一個前綴一個后綴，使得這兩個字符串相同。 輸出所有可能的情況。

如aaaaa,
aaaaa ——》OK
aaaaa ——》OK
aaaaa + aaaaa  ——》OK
aaaaa + aaaaa  ——》OK
aaaaa + aaaaa ——》OK

那么這個題怎么用next呢，其實很簡單，只要你知道next的含義。 s[1]——s[next[len]]中的內容一定能與s[1+len-next[len]]——s[len]匹配，所以s[1]——s[next[len]]就是我們要求取的最長的那個串，然后呢我們循環地利用next,由于next的性質，可以保證，每一次得出的字串都能匹配到最后一個字母，也就是得到一個前綴等于后綴。只不過這個字符串的長度在不斷地減小罷了。不斷地使用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])//上一個循環可能因為j=-1而不做，此時不能知道s[i]與s[j+1]的關系。故此需要此條件。
            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;
    
}

文章寫完了，如果有什么疏漏，還請大家批評指正~
文章來自abilitytao博客
轉載請注明出處：http://www.shnenglu.com/abilitytao/archive/2009/08/01/91865.html

posted on 2009-08-01 10:26 abilitytao 閱讀(3088) 評論(3)  編輯 收藏 引用