nextval演算法

① KMP演算法中的nextval函數值的原理，求詳細推導

1 get_nextval(int *nextval,const char *string)
2 {
3 int num=strlen(string);
4 int i=0,j=-1;
5 nextval[0]=-1;
6 while(i<num)
7 {
8 if(j==-1||string[i]=string[j])
9 {
10 i++;
11 j++;
12 if(string[i]==string[j])
13 {
14 nextval[i]=nextval[j];
15 }
16 else
17 {
18 nextval[i]=j;
19 }
20 }
21 else
22 {
23 j=next[j];
24 }
25 }
kmp的思想主要是通過nextval數組來指示「假如在子串與主串匹配過程中在某一位(假設為 j )匹配失敗（不相等）時，子串應回到的位置。」以此區別於樸素模式匹配的一旦在某位匹配失敗，就從頭比較的特點。所以在生成與子串等長的nextval數組時，nextval數組每一個元素標識的就應該是當在子串的第j位與主串匹配失敗時，應回到子串的哪一位。
設子串string為"abqabc"。主串為"abqabqabc"；生成nextval的思想是：假設目前 j 和 i 各處string的某一個位置，對比string[j]和string[i]（代碼第8行），若相等，j 和 i 都向前一步，j , i 向前一步（代碼10~11行）是為了下一次匹配，同時是為了在nextval[i]記錄當子串與主串匹配失敗時應回到子串的哪一位繼續比較下去（代碼第14或18行）。比如說當子串與主串在第六位（子串的c跟主串的q）匹配失敗時，我們會希望nextval[5]記錄的是2，這樣"ab"就不需重新匹配。
可以看到在子串的 c 之前，"abqab" 是前綴(ab)與後綴(ab)相等的，有兩位，所以在nextval[5]記錄 2 ，意思就是當 c 與主串匹配失敗時，直接回到子串string[2]繼續比較即可。
在製作nextval數組的過程中，i只會往前，j如果遇到前綴string[j]不等於後綴string[i]時會回溯，往回找，看能不能找到與後綴相等的前綴。比如子串為"abqabac"，製作nextval數組時比較到第三位(q)跟第六位(a)時，此時q不等於a，所以j往回找，拿第二位（b）跟第六位（a）比較，還是不相等，繼續往回找，找到一個位（a）跟第六位（a），相等，則在nextval[5]記錄nextval[0]的值，即-1，這時如果子串跟主串的匹配在子串的第六位（a）匹配失敗了，則直接略過主串的這一位，子串從頭開始與主串的下一位繼續進行匹配。

② 數據結構與演算法串的模式匹配

1.簡單的模式匹配演算法
子串的定位通常稱為串的模式匹配，它求的是子串的（常稱模式串）在主串中的位置

實現思想：
將主串中與模式串長度相同的子串摘出來，按個與模式串對比

缺點：主串指針會出現回溯現象導致時間開銷增加

最壞時間復雜度：O(mn)，其中m和n分別代表主串和模式串的長度

2.KMP演算法
字元串的前綴、後綴和部分匹配值

next數組：當模式串的第j個字元匹配失敗時，令模式串跳到next[j]再繼續匹配

時間復雜度：O(m+n)

優點：主串不會進行回溯

3.KMP演算法優化
當子串和模式串不匹配時j=nextval[j],通過構造nextval函數