next數組兩種求法

一、說明

（１）看到網上同一個字元串求 next 數組的值有兩種，一種是 -1 開頭，一種是 0 開頭，雖然有差别，但是以 0 開頭的next數組的每一項都比以 -1 開頭的next數組的對應項大1，是以，具體是以 0 開頭還是以 -1 開頭看需要吧，算法都是一樣的．KMP 的原始論文 （K，M，P 三個家夥寫的原文）中是以 0 開頭的，是以下面的寫法是以 0 開頭的．

（２）關于 next 數組的求法，網上能找到很多流行簡潔的寫法，也有很多文章對簡潔代碼講解得非常細緻，然而本文并不是對流行算法的剖析，而隻是記錄一下自己比較喜歡的計算方法，并用代碼實作一下．

二、求法的文字描述

（1）第一種求法：根據前一個字元的next值求字元串記作 p；next 數組記作 next；

約定：

• 下标從 1 開始算，注意，不是從 0 開始算
• 字元串長度 >2

1）第一個字母的 next 值置 0 （next[1] = 0），第二個字母的 next 值置 1（next[2] = 1） ；

2）從第 3 個開始，計算第 i 個位置的 next 值時，檢查

p[i-1]== p[next[i-1]] ?（即這兩個值是否相等）

解釋：第 i 個位置的前一個位置的值（即 p[i-1]，記作 m）與以 m 的 next 值（即 next[i-1]）為下标的值（即 p[next[i-1]]，記作 n）是否相等，（看的懵懵的也沒關系，後面會有例子）

• 若相等，則 next[i] = next[i-1] + 1

• 若不等，則繼續往回找，檢查

  p[i-1]== p[next[next[i-1]]] ?

  • 若相等，則 next[i] = next[next[i-1]] + 1
  • 若不等，則繼續往回找，直到找到下标為 1 還不等（即字元串第一個元素），直接指派 next[i] = 1

（2）第二種求法：根據最大公共元素長度求

首先附上講解的博文位址，裡面有詳細講解

http://blog.csdn.net/v_july_v/article/details/7041827

1）算出每一個字母字首字尾的最大公共元素長度

2）最大公共元素長度整體向後移動一個長度，最前面的元素值填 -1，即為 next 數組的第一版本

3）（如果你需要的 next 數組第一個值為 -1，這步就可以省略了）next 數組的每一個值分别+1，即求得 next 數組。

三、執行個體

字元串 P =“ababaaababaa”

求解：

（1）對應上面第一種求法

1）初始化

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	1

2）求下标為 3 的字元的 next 值

P[3-1] = P[2] = ‘b’;

next[3-1] = next[2] = 1 ;

P[next[3-1]] = P[1] = ‘a’;

P[3-1] != P[next[3-1]] ，但是此時已經回溯到了第一個元素，

∴ 直接P[3] = 1 ;

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	1	1

3）求下标為 4 的字元的 next 值

P[4-1] = P[3] = ‘a’;

next[4-1] = next[3] = 1 ;

P[next[4-1]] = P[1] = ‘a’;

P[4-1] == P[next[4-1]] ;

∴ next[4] = next[4-1] + 1 = 2 ;

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	1	1	2

4）求下标為 5 的字元的 next 值

P[5-1] = P[4] = ‘b’;

next[5-1] = next[4] = 2 ;

P[next[5-1]] = P[2] = ‘b’;

P[5-1] == P[next[5-1]] ;

∴ next[5] = next[5-1] + 1 = 3 ;

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	1	1	2	3

5）求下标為 6 的字元的 next 值

推導過程同上 => next[6] = next[6-1] + 1 = 4 ;

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	1	1	2	3	4

6）求下标為 7 的字元的 next 值

P[7-1] = P[6] = ‘a’;

next[7-1] = next[6] = 4 ;

P[next[7-1]] = P[4] = ‘b’;

P[7-1] != P[next[7-1]] && 此時還未回到第一個，繼續

next[next[7-1]] = next[4] = 2 ;

P[next[next[7-1]]] = P[2] = ‘b’;番外（1）

P[7-1] != P[next[next[7-1]]] && 但是此時還未回到第一個，繼續

next[next[next[7-1]]] = next[2] = 1 ;

P[next[next[next[7-1]]]] = P[1] = ‘a’ ;

P[7-1] == P[next[next[next[7-1]]]] ;

∴ next[7-1] = next[next[next[7-1]]] + 1 = next[2] + 1 = 2 ;

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	1	1	2	3	4	2

7）求下标為 8 的字元的 next 值

P[8-1] = P[7] = ‘a’；

next[8-1] = next[7] = 2 ;

P[next[8-1]] = P[2] = ‘b’;

P[8-1] != P[next[8-1]] ,但是還沒回到第一個元素，繼續

next[next[8-1]] = next[2] = 1 ;

P[next[next[8-1]]] = P[1] = ‘a’;

P[8-1] == P[next[next[8-1]]];

∴ next[8] = next[next[8-1]] + 1 = 2

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	1	1	2	3	4	2	2

8）求下标為 9 的字元的 next 值

推導過程同4) => next[9] = next[9-1] + 1 = 3 ;

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	1	1	2	3	4	2	2	3

9）求下标為 10 的字元的 next 值

推導過程同4) => next[10] = next[10-1] + 1 = 4 ;

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	1	1	2	3	4	2	2	3	4

10）求下标為 11 的字元的 next 值

推導過程同4) => next[11] = next[11-1] + 1 = 5 ;

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	1	1	2	3	4	2	2	3	4	5

11）求下标為 12 的字元的 next 值

推導過程同4) => next[12] = next[12-1] + 1 = 6 ;

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	1	1	2	3	4	2	2	3	4	5	6

（2）對應上面第二種求法

1）算出每一個字母字首字尾的最大公共子串長度（下一步會把最後一位移走，是以最後一位可以不算）番外（2）

P	a	b	a	b	a	a	a	b	a	b	a	a
前字尾最大公共子串長度	1	2	3	1	1	2	3	4	5

2）最大公共子串長度整體向後移動一個長度，最前面的元素值填 -1，即為 next 數組的第一版本

P	a	b	a	b	a	a	a	b	a	b	a	a
next 數組第一版	-1	1	2	3	1	1	2	3	4	5

3）（如果你需要的 next 數組第一個值為 -1，這步就可以省略了）next 數組的每一個值分别+1，即求得 next 數組。

P	a	b	a	b	a	a	a	b	a	b	a	a
next 數組第二版	1	1	2	3	4	2	2	3	4	5	6

四、代碼實作

（１）對應上面第一種方法

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

class Solution{
public:
    vector<int> getNext2(string ps){
        vector<int> next;
        int l = (int)ps.length();
        if(l ==  ){
            return next;
        }else if(l == ){
            next.push_back();
            return next;
        }else if(l == ){
            next.push_back();
            next.push_back();
            return next;
        }
        char p[];
        strcpy(p, ps.c_str());//字元串轉字元數組
        next.push_back();
        next.push_back();
        for(int i = ;i<(int)ps.length();i++){
            int k = next[i-];
            while(k!=){
                if(p[i-] == p[k-]){//k-1是因為，在計算機裡，數組下标是從0開始的
                    next.push_back(k+);
                    break;
                }else{
                    k = next[k-];
                }
            }
            if(k==) {
                next.push_back();
            }
        }
        return next;
    }
};
           

（2）對應上面第二種方法

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

class Solution{
public:
    vector<int> getNext2(string ps){
        vector<int> next;
        int l = (int)ps.length();
        if(l ==  ){
            return next;
        }else if(l == ){
            next.push_back();
            return next;
        }
        next.push_back();//next數組第一個值為0
        for(int i = ; i < l-; i++ ){//最後一個最大公共子串長度不用算
            //計算每一個子字元串的字首字尾最大公共子串長度
            int l = max_pub_substr(ps.substr(,i+));
            //右移後+1
            //for循環之前已加了一個資料0進next數組，此時再加進去元素時，元素在next數組裡的下标比得到該元素值的子串最後字元的下标大１，也就相當于向後移一位了
            next.push_back(l+);
        }
        return next;
    }
    //計算字首字尾的最大公共子串長度
    int max_pub_substr(string ps){
        int l = (int)ps.length();
        if(l ==  || l == ){
            return ;
        }
        char p[];
        strcpy(p, ps.c_str());//字元串轉字元數組
        int len = ;
        int m = -;//最後一個字元（不包括）之前與最後一個字元相等的字元下标 ｍ
        int k = -;//已經查找過的字元下标
        while( k != l- ){
            k = m+;
            for(; k < l-; k++){
                if(p[k] == p[l-]){
                    m = k;
                    break;
                }
            }
            if( m==- || k==l+){//表示沒有與最後一個字元相等的字元
                return len;
            }else{//檢查字首串和字尾串是否相等
                int i = ,j = l--m;
                for(; i <= m,j < l; i++,j++){//i字首下标,j字尾下标
                    //隻要有不相等的就失敗
                    if(p[i] != p[j]){
                        break;
                    }
                }
                if( i == m+ ){//說明前後串相等，因為全都比較了，沒有中斷
                    len = m+;
                }
            }
        }
        return len;
    }
};
           

五、驗證

int main(){
    string s = "ababaaababaa";
    Solution slt;
    vector<int> next = slt.getNext2(s);
    vector<int>::iterator it;
    for( it = next.begin(); it != next.end(); it++){
        cout<<*it;
    }
    return ;
}
           

六、番外

（1）在這個地方，我們可以發現，P[2] == P[4] == ‘b’ ，由于P[4] != P[6] ，∴ P[2] != P[6] 是一定的，就可以跳過 P[2] 和 P[6] 的比較，直接比較 P[1] 和 P[6]；

（2）字首字尾的最大公共元素長度

• 字首：簡單來說，也就是，從第一個字母（必包括）開始往後看到最後一 個字母（不包括）為止的字元串的以第一個字母開頭的子串

  （比如“abab”的字首有a,ab,aba）;

• 字尾：簡單來說，也就是，從最後一個字母（必包括）開始往前看到第一個字母（不包括）為止的字元串的子串

  （比如“abab”的字尾有b,ab,bab）;

• 最大公共子串長度：也就是字首和字尾擁有的相同子串的最大長度

  以“abab”為例：

模式串的各個子串	字首	字尾	最大公共元素長度
a	空	空
ab	a	b
aba	a,ab	a,ba	1
abab	a,ab,aba	b,ab,bab	2

一種稍微快一點的小方法：

“abab”前字尾的公共子串必然是以 a（字元串第一個字母） 開頭，b（字元串最後一個字母）結尾的子串，“abab”的字首串中滿足條件的子串集合為A={“ab”}，字尾串中滿足條件的子串集合為B={“ab”}，再找出A,B集合中相等的子串集合C，最後算出C中最長子串的長度即為最大公共子串長度。

好啦~~~寫了這麼多，我自己都懶得看T_T