KMP算法

看嚴蔚敏的數據結構看得云里霧里，后來看了 其它博客 才了解得比較透徹。其實算法的大體思路并不難理解。最原始的字符串匹配算法是將匹配串與模式串對齊，然后從左向右一個個比較，如果失配則模式串向右移動一個單位，這樣沒有利用前面部分匹配的信息，時間復雜度為O(n*m)。

KMP算法則是利用了部分匹配的信息，并以此來判斷失配時向右移動多少，時間復雜度為O(n+m)。設i指向匹配串的當前匹配字符，j指向模式串的當前匹配字符，若失配，則j=next[j]。

因此關鍵就是求模式串的next數組。嚴蔚敏的教材是針對從1開始的數組的，而且對next數組的值的意義也沒說清楚，所以在那里卡了很久，看了其他人的博客才清楚。

要理解next數組還是比較難的，教材上的思路是這樣的：

已知next[0]=-1,next[1]=0，設next[j]=k，若t[j]==t[k]且t[j+1]!=t[k+1]，則next[j+1] =next[j]+1；若t[j]==t[k]且t[j+1]==t[k+1]，則next[j+1] = next[k+1]。若t[j]!=t[k]，可以看成模式串自身匹配問題，將模式向右滑動到next[k]，若還是不匹配，就滑動到next[next[k]]，如果最后還是不匹配則就肯定會滑動到next[0]。所以下面的程序會看到if(j ==-1 ||...)

next數組的取值(設模式串為t[])

next[0]=-1 任何模式串的第一個模式值規定為-1

next[j] = -1 （j>k≥1） 若t[j] = t[0]且前k個字符不等于j前面的k個字符，則模式值為-1（這表示第一個字符都無法匹配）

next[j] = k   （j>k≥1）t[j]!=t[k]且前k個字符等于j前面的k個字符

next[j] = 0  其它情況。這里有三種情況，一種是對于j>k≥1，前k個字符不等于j前面的k個字符且t[j]!=t[0]，自然需要滑動到第一個字符再開始匹配；一種是對于j>k≥1，前k個字符等于j前面的k個字符且t[j]==t[0]，讓它直接滑動到第一個字符(因為next[k]會是0)，能夠減少比較次數；還有一種就是next[1]總是為0

代碼如下

inline void get_next(string t, int next[])
{
    int i = 0, j = -1;
    next[0] = -1;
    while (i<t.length())
    {//j在每次循環開始都表示next[i]的值，同時也表示需要比較的下一個位置 
        if (j == -1 || t[i] == t[j])
        { 
            ++i; 
            ++j;
            if (t[i] != t[j])
                next[i] = j;
            else
                next[i] = next[j];
        }
        else j = next[j];
    }
}

int KMP(string s, string t)
{
    int i = 0, j = 0;
    int s_len = s.length();
    int t_len = t.length();
    int *next = new int[t_len + 1];
    get_next(t, next);
    while (i<s_len && j<t_len)
    {
        if (j==-1 || s[i] == t[j]) { ++i; ++j; }
        else
            j = next[j];
    }
    if (j>=t_len) return i - t_len; //匹配成功
    else return -1;
}