- 问题：给定字符串target，找子字符串pattern是否存在
- followup: 第一个出现pattern的位置，及所有出现pattern的位置
例子：
- 输入：
target = "ABDABABACEE"
pattern = "ABABAC"
- 输出：
true
思路：
- 子问题 1. 建立pattern对应的DFA（有限确定状态机）
- 子问题 2. target 作为DFA 输入，得到是否AC状态
子问题1.
DFA 定义：https://en.wikipedia.org/wiki/Deterministic_finite_automaton
1. 所有状态：以prefix substring 作为状态, 取个例子 pattern=”ABABAC“
{"", "A", "AB", "ABA", "ABAB", "ABABA", "ABABAC"}
2. 起始状态：“” (属于 所有状态集合)
3. Final 状态集合：{“ABABAC”} (包含于 所有状态集合)
4. 输入的字符集合： {‘A’, 'B', 'C', ...}
5. 状态转移函数（以下两种方式等价）
1. 画出状态图 (易于理解)
2. 建立状态转移表（易于写代码）
总结子问题1： 理解DFA 模型后，问题转化成 --- 如何构建状态转移表
建立状态表注意： 是否吃掉输入的字符，即遇到了不匹配的字符，是否转移到，当前的不匹配状态。
子问题2.
// 核心一行代码：j = next[j - 1]; 失配后回退到哪
public static int indexOfKMP(String source, int sourceLen, String pattern, int patternLen, int[] next) {
int s = 0, p = 0;
while (s < sourceLen && p < patternLen && patternLen <= sourceLen) {
if (source.charAt(s) == pattern.charAt(p)) {
++ s; ++ p;
} else {
if (p == 0) ++ s;
else p = next[p - 1];
}
}
return p == patternLen ? s - patternLen : -1;
}
public static int[] getNextII(String s) {
int len = s.length();
int[] next = new int[len];
for (int i = 1; i < len; ++ i) {
int j = next[i - 1];// matched len
while (j > 0 && s.charAt(i) != s.charAt(j)) j = next[j - 1]; // 如何回退
if (s.charAt(i) == s.charAt(j)) next[i] = j + 1;
else next[i] = 0;
}
return next;
}
