Ⅰ KMP演算法next數組的計算
字元串如果是以0為下標的話next[7]是0，只有最後一位與第一位相等
Ⅱ kmp演算法中的next到底是什麼意思啊
先看看next數據值的求解方法
位序 1 2 3 4 5 6 7 8
模式串 a b a a b c a c
next值 0 1 1 2 2 3 1 2
next數組的求解方法是：
1.第一位的next值為0
2.第二位的next值為1
後面求解每一位的next值時，根據前一位進行比較
3.第三位的next值：第二位的模式串為b ,對應的next值為1;將第二位的模式串b與第一位的模式串a進行比較，不相等；則第三位的next值為1
4.第四位的next值：第三位的模式串為a ,對應的next值為1;將第三位的模式串a與第一位的模式串a進行比較，相同，則第四位的next值得為2
5.第五位的next值：第四位的模式串為a，對應的next值為2;將第四位的模式串a與第二位的模式串b進行比較，不相等；第二位的b對應的next值為1,則將第四位的模式串a與第一位的模式串a進行比較，相同，則第五位的next的值為2
6.第六位的next值：第五位的模式串為b，對應的next值為2;將第五位的模式串b與第二位的模式中b進行比較，相同，則第六位的next值為3
7.第七位的next值：第六位的模式串為c，對應的next值為3;將第六位的模式串c與第三位的模式串a進行比較，不相等；第三位的a對應的next值為1，則將第六位的模式串c與第一位的模式串a進行比較，不相同，則第七位的next值為1
8.第八位的next值：第七位的模式串為a，對應的next值為1;將第七位的模式串a與第一位的模式串a進行比較，相同，則第八位的next值為2
以上這種分析方法，位序是從1開始的，如果位序從0開始，剛第一位的next值為-1,後面的方法則相同
Ⅲ KMP演算法求next數組的問題
字元串以0為下標時，next[7]為0，說明只有最後一位與第一位相等。在第i個字元前的i-1個字元中，從開頭開始的1個字元與最後1個字元相等，則next[i]=0；如果不等，則next[i]=1；從開頭開始的2個字元與最後2個字元相等，則next[i]=1；如果不等，則next[i]=2；依此類推。
前綴next數組的求解演算法如下：
void SetPrefix(const char *Pattern, int prefix[]) {
int len=CharLen(Pattern);//獲取模式字元串長度。
prefix[0]=0;
for(int i=1; i < len; i++) {
int j=prefix[i-1];
while(j>0 && Pattern[i]!=Pattern[j])
j=prefix[j-1];
if(Pattern[i]==Pattern[j])
j++;
prefix[i]=j;
}
}
演算法中，通過比較模式字元串的前綴與後綴，來逐步構建next數組。當模式字元串發生變化時，需要重新計算next數組。這個演算法的時間復雜度為O(n)，其中n為模式字元串的長度。
next數組的構建過程中，若前綴與後綴不匹配，則將前綴索引回退到已知匹配的位置，繼續進行比較。這樣可以避免不必要的重復比較，提高演算法效率。
在KMP演算法中，next數組用於記錄模式串中每個位置的最長相等前後綴長度。通過next數組，可以快速跳過已匹配的部分，從而提高字元串匹配的效率。
Ⅳ 模式匹配KMP演算法裡面next里保存的值有什麼用
next數組存儲的數據是用來當模式串與主串不匹配的時候要模式串回退到第幾個字元與主串再重新匹配，我們知道KMP演算法的主串是不回朔的，當不匹配的時候我們不是退回到開始位置重新匹配，而是利用已經匹配的結果將模式串回朔到下一個位置，這個位置比開始位置更近一步;
簡單的說就是next[ j ]的值保存的是當模式串中第 j 個字元與主串第 i 個字元不匹配時候，模式串中的哪個字元 重新與主串第 i 個再匹配，這樣總的字元比較次數比從開始位置比較的次數就少了。