kmp演算法next數組前兩個

Ⅰ 給出字元串在KMP演算法中的Next數組

逐個查找對稱串。

只要循環遍歷這個子串，分別看前1個字元，前2個字元，3個... i個 最後到15個。

第1個a無對稱，所以對稱程度0

前兩個ag無對稱，所以也是0

依次類推前面0-4都一樣是0

最後一個是0～3都一樣是0

前綴next數組的求解演算法：

void SetPrefix(const char *Pattern, int prefix[])

{

int len=CharLen(Pattern);//模式字元串長度。

prefix[0]=0;

for(int i=1; i<len; i++)

{

int k=prefix[i-1];

//不斷遞歸判斷是否存在子對稱，k=0說明不再有子對稱，Pattern[i] != Pattern[k]說明雖然對稱，但是對稱後面的值和當前的字元值不相等，所以繼續遞推

while( Pattern[i] != Pattern[k] && k!=0 )

k=prefix[k-1]; //繼續遞歸

if( Pattern[i] == Pattern[k])//找到了這個子對稱，或者是直接繼承了前面的對稱性，這兩種都在前面的基礎上++

prefix[i]=k+1;

else

prefix[i]=0; //如果遍歷了所有子對稱都無效，說明這個新字元不具有對稱性，清0

}

}

(1)kmp演算法next數組前兩個擴展閱讀：

設主串（下文中我們稱作T）為：a b a c a a b a c a b a c a b a a b b

模式串（下文中我們稱作W）為：a b a c a b

用暴力演算法匹配字元串過程中，我們會把T[0] 跟 W[0] 匹配，如果相同則匹配下一個字元，直到出現不相同的情況，此時會丟棄前面的匹配信息，然後把T[1] 跟 W[0]匹配，循環進行，直到主串結束，或者出現匹配成功的情況。這種丟棄前面的匹配信息的方法，極大地降低了匹配效率。

而在KMP演算法中，對於每一個模式串我們會事先計算出模式串的內部匹配信息，在匹配失敗時最大的移動模式串，以減少匹配次數。

Ⅱ 那個，KMP演算法裡面 求模式串的next[]數組的方法看不懂； 有大神能詳細解釋一下不，看不懂哇

對於next[]數組
也就是子串的某個位置與自身的公共前綴的最後匹配位置。
這樣講可能有點抽象，說白了就是子串以該位置為最末位，自己和自己匹配的最長公共前綴。

而在進行next[]數組的第i個位置的求值時，該位置以前的所有next[]值已經求出，因此我們可以藉助之前求出的next[]值來更新此刻next[i]的值。

所以時間復雜度為O(2*m)

拿ababac來說：
第一步：
ababac
_ababac
i，j在一開始就失配，即next[2]=0。

第二步：
ababac
__ababac
i，j在第3位匹配，next[3]=1
同理：next[4]=2，next[5]=3，next[6]=4

在i=6，j=4時失配。

因此，將j=next[j]+1，i++，也就是匹配串後移。
即：
ababac
______ababac
此時，兩串失配，next[7]=0

求next[]數組代碼：
int next[100];
char str2[100];
void get_next()
{
int len2=strlen(str2);
int i=1,j=0;
while(i<len2)
{
if(j==0 || str2[i]==str2[j])
{
i++;j++;
next[i]=j;
}
else
j=next[j];
}
}

Ⅲ KMP演算法中的next數組如何計算

next[i]表示的是：
在第i個字元前面的i-1個字元裡面，
從開頭開始的1個字元與最後1個字元是否相等，若不是，則next[i]=0,否則繼續看下面；
從開頭開始的2個字元與最後2個字元是否相等，若不是，則next[i]=1,否則繼續看下面；
從開頭開始的3個字元與最後3個字元是否相等，若不是，則next[i]=2,否則繼續看下面；
……
就是這樣的判斷取值。
它的意思就是如果到了某個字元不匹配的情況時候，你就可以直接把模式串拖到從開頭開始的那next[i]個字元等於當前字元的前next[i]個字元的地方，這樣就少了很多重復的無效的比較和移動。