在我20年寫的這篇文章里，已經把DFA給講的比較透徹了。但重讀了一下NFA的部分，還是有些瑕疵。打算這次希望把它講透，下次再理解KMP的NFA解法時（又稱next數組解，或不確定有限狀態(tài)機解），可以一目了然。
行文的用詞
- 待匹配的文本為str（string的縮寫）
- 要匹配的串為pat(pattern的縮寫),
step1. nfa 數組的定義
KMP-NFA解的第一步就是構建NFA（NEXT）數組
int[] nfa = new int[pat.length];
這個數組的作用是 當pat[j] ！= str[i] 的時候，nfa[j]存的是我們下一個值得一試的J的位置在哪？
如果是確定狀態(tài)機，我能明確知道
J該變到什么位置（一次成功）；但是再非確定的狀態(tài)機下，我能明確知道這個J是值得一試的（當次可能成功可能失敗，需要試多次）
如果感興趣KMP的確定狀態(tài)機是怎么實現的，可以看我上面提供的那個鏈接，20年寫的那篇博客
如下圖的紅色框：
長串的C 和 匹配串的最后一個D 失配了，也就是我們之前 說的
pat[j] ！= str[i] 的時候；可以看到當時J = 6, nfa[6] = 2; 為2的原因也就是圖中的藍色框。帶匹配文本的索引I之前的后綴AB，等于匹配串的前綴AB;所以如果我們把NFA數組的每個數字都左移1格，也就是
nfa[i - 1] = nfa[i], 那存的就是最長的公共前后綴(縮寫為lcx)。
比如
pat[]: A B C D A B
lcx[]: 0 0 0 0 1 2
nfa[]:-1 0 0 0 0 1 2
上面NFA，是不帶優(yōu)化的NFA。也就是在STEP 3時，即使字符相同，也去試一下。有時為了構建最長公共前后綴數組，會不做step3的那個優(yōu)化；
step2. nfa 數組的初始化
int[] nfa = new int[pat.length];
nfa[0] = -1;
for (int i = 1, j = 0; i < nfa.length; i++) {
// 下面是進入循環(huán)必須要符合的不變量（如果不變量不成立，則算法有BUG）
assert pat.substring(0, j).equals(pat.substring(i - j, i));
for (int k = j + 1; k < i; k++) assert !pat.substring(0, k).equals(pat.substring(i - k, i));
}
nfa[0] = -1 因為如果待匹配的字符串第一個字符，和當前文本的字符就不一致。那么直接可以i++, j++; 看文本下一個字符是否能和待匹配的字符串第一個字符去匹配了。所以根據上一步的NFA的定義，J應該是-1;
其實我們也可以把-1的位置理解為正則的*, 一個萬能字符
既然0的值很清楚了。下面我們的目標就是要把 NFA 數組的 從1到NFA.LENGTH -1 的值給確定出來。
所以有 for (int i = 1; i < nfa.length; i++)
那么I也就定義明白了。
為了給NFA賦值，我們需要另外一個指針J。這個J的作用正如我們上面提到的，邏輯鏈路是這樣的。
- NFA[I] 是在失配（下圖紅框）時，下一個值得嘗試的位置。
- 下一個值得嘗試的位置，必然是在
pat[0:i-1]里存在一個最大的J，使得pat[0:j) == pat[i - 1 - j:i)(注意[x,y)表示前閉后開區(qū)間）。這個等式，就是下圖藍框。
image.png - 那么我們就需要一個變量來存這個J。有了J我們就可以很依靠這個J去構建NFA
要驗證的不變量
上面我們講清楚了I和J的意義，也非常好理解進入循環(huán)開始時，我們要驗證的不變量。注意JAVA里的substring(x,y)表示前閉后開區(qū)間！
-
assert pat.substring(0, j).equals(pat.substring(i - j, i));表示滿足前后綴相等 -
for (int k = j + 1; k < i; k++) assert !pat.substring(0, k).equals(pat.substring(i - k, i));表示J是滿足前后綴相等這個條件里，在[0,i-1]這個范圍里最大的
那么在 I = 1的情況下，J的初始值只能為0. 來滿足上面的不變量。
step3. 給NFA賦值
既然，我們進入循環(huán)內，滿足上面的2個不變量條件。
那么J 其實就是NFA[I]的值了。
int[] nfa = new int[pat.length];
nfa[0] = -1;
for (int i = 1, j = 0; i < nfa.length; i++) {
// 下面是進入循環(huán)必須要符合的不變量（如果不變量不成立，則算法有BUG）
assert pat.substring(0, j).equals(pat.substring(i - j, i));
for (int k = j + 1; k < i; k++) assert !pat.substring(0, k).equals(pat.substring(i - k, i));
nfa[i] = j;
}
如果需要求得最長公共前后綴數組，則不能用下面的優(yōu)化；上面的代碼也是WORK的，就是效率會低一點。
當然這么寫是沒有問題的，但是破壞了一個我們之前對NFA數組的一個定義，就是存的是值得一試的J。
想一下我們的 PAT[I] 如果和 STR[K] 已經匹配失敗了str[k] != pat[i]。 我們下一個值得試的位置是NFA[I]，如果pat[nfa[i]] == pat[i]，必然就會有 str[k] != pat[nfa[i]]; 那么我們其實可以保證我們NFA[I]里存的下一個位置J，這個J所在的字符和I所在的字符得不一樣。這樣這個J才能算值得嘗試。（通過I就能知道的必敗的J不值得一試）；所以正確的代碼如下:
int[] nfa = new int[pat.length];
nfa[0] = -1;
for (int i = 1, j = 0; i < nfa.length; i++) {
// 下面是進入循環(huán)必須要符合的不變量（如果不變量不成立，則算法有BUG）
assert pat.substring(0, j).equals(pat.substring(i - j, i));
for (int k = j + 1; k < i; k++) assert !pat.substring(0, k).equals(pat.substring(i - k, i));
nfa[i] = pat[i] != pat[j] ? j : nfa[j];
}
雖然J滿足2個不變量，但是因為pat[i] == pat[j],，J依賴不值得一試，所以不能寫進NFA[I]里
既然NFA里要求存的是值得一試的J，NFA[I]要存的是在根據當前的J的位置去NFA里找下一個值得一試的J，也就是NFA[J]。
舉個例子：
雖然紅框的第三行，也滿足2個不變量，但是因為紅框右側都是D，所以不值得一試，不如直接選擇滿足不變量1的但是字符不同的藍色框第四行去嘗試，來的高效
因為是從NFA里取出來的，必然滿足pat[i] != pat[nfa[j]], 如果找不到這樣的nfa[j]，nfa[j]里也會存著-1來兜底。
比如 aa 的 nfa數組 就是 [-1, -1]
step4. 更新J用來保護下一個循環(huán)不變量不被破壞
這個NFA[I] 搞定之后，迎接我們的就是下一輪循環(huán)，I 會+1；所以我們必須要在進入下一個循環(huán)前，去更新J以滿足下一個循環(huán)下和I+1合作的時候，不變量不被破壞。
情況1 pat[i] == pat[j]
這個時候因為前面的不變量有 assert pat.substring(0, j).equals(pat.substring(i - j, i));
那么即使I++, J++后，這個不變量依然存在因為 pat.substring(0, j+1).equals(pat.substring(i - j, i+1))
情況2 pat[i] ！= pat[j]
如下圖P[J] != P[K] (P數組含義等價于PAT數組，只是不同叫法)
我們應該讓K = NEXT[K] (next數組和NFA數組是一個意思,為了配合圖片用NEXT數組表述這段）；因為NFA的定義
P[k] != P[next[k]]所以就有可能使得
P[next[k]] == P[J] ，如果還失敗了，就繼續(xù)用NEXT數組找下一個，一直會到-1去兜底。因為走的是NEXT數組，一旦相同了，公共前后綴的性質必定滿足。那么前綴和后綴都同時加上一個同樣的字符，那么必定還是滿足公共前后綴性質。因為J是單調遞減的，J > NFA[J] > NFA[NFA[J]] ; 所以最大的J這個性質也可以滿足。
通過上面的方法，我們就知道如何維護J了。也就得出KMP 構建NFA數組的全部代碼
int[] nfa = new int[pat.length()];
nfa[0] = -1;
for (int i = 1, j = 0; i < nfa.length; i++) {
// 下面是進入循環(huán)必須要符合的不變量（如果不變量不成立，則算法有BUG）
assert pat.substring(0, j).equals(pat.substring(i - j, i));
for (int k = j + 1; k < i; k++) assert !pat.substring(0, k).equals(pat.substring(i - k, i));
nfa[i] = pat[i] != pat[j] ? j : nfa[j];
while (j >= 0 && pat[i] != pat[j]) j = nfa[j];
j++;
}
step5. 使用NFA
leetcode 28題
https://leetcode.com/problems/implement-strstr/
public int strStr(String strr, String patt) {
char[] str = strr.toCharArray(), pat = patt.toCharArray();
int[] nfa = new int[pat.length];
if (nfa.length == 0) return 0;
nfa[0] = -1;
for (int i = 1, j = 0; i < nfa.length; i++, j++) {
// 下面是進入循環(huán)必須要符合的不變量（如果不變量不成立，則算法有BUG）
assert patt.substring(0, j).equals(patt.substring(i - j, i));
for (int k = j + 1; k < i; k++)
assert !patt.substring(0, k).equals(patt.substring(i - k, i));
// 不變量驗證結束，不變量驗證的代碼可在測試后，注釋掉
nfa[i] = pat[i] != pat[j] ? j : nfa[j];
while (j >= 0 && pat[i] != pat[j]) j = nfa[j];
}
// 下面是NFA數組的使用部分
int i = 0, j = 0;
for (; i < str.length && j < pat.length; i++, j++) {
while (j >= 0 && str[i] != pat[j]) j = nfa[j];
}
return j == pat.length ? i - j : -1;
}
