KMP 自动机解释

• 问题：给定字符串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;
    }