字符串匹配算法KMP原理

KMP算法是一种字符串匹配算法，解决从文本串为"ABABDABACDABABCABAB"中查询模式串为"ABABCABAB"位置的一种算法。它是暴力循环匹配（从文本串的第一个字符开始，对模式串进行循环匹配，如果不匹配，文本串下移一个字符，继续跟模式串匹配）的一种优化。

原理：

设置文本串为 ababadeabc，模式串为ababaca，从第一个字符进行匹配：

ababadeabcababaca
ababaca
 
模式串匹配到ababa下一个字符就无法匹配了：
ababa->d
ababa->c

如果从文本串的第二个字符继续匹配，那么就浪费了已经匹配获得的信息，根据第一步匹配的信息，文本串中的ababa已经和模式串的ababa一致，模式串中的ababa已包含一个关键的跳跃查询信息：

文本串：ababa
模式串：ababa
 
模式串直接跳跃至：
文本串：ababa
模式串：  ababa

根据跳跃信息，则可直接实现有限范围内的最长匹配，因为根据已有信息是不知道文本串ababa后面是什么，但是知道这么跳跃后可以直接匹配aba三个字符，节省匹配时间。

这个跳跃信息的依据跟文本串无直接关系，跟模式串的公共最长前后缀信息有关：ababaca，长度是7，子串分别是a，ab，aba，abab，ababa，ababac，ababaca，它们的公共最长前后缀分别是0,0,a,ab,aba,0,a。注意上例中已匹配成功的ababa的公共最长前后缀就是aba，就是跳跃后可以直接匹配aba三个字符。

最长公共前后缀是指一个字符串的最长的前缀和后缀，它们是相同的。注意这里的前缀和后缀不能包括整个字符串。
 
例如，对于字符串"ABAB"：
 
- 它的前缀有："A", "AB", "ABA", "ABAB"
- 它的后缀有："B", "AB", "BAB", "ABAB"
 
在这些前缀和后缀中，"AB"是最长的公共前后缀。

以上就是KMP的思想原理，求字符串的各个子串公共最长前后缀长度代码如下：

    public int[] computePrefixFunction(String pattern) {
        int[] prefixFunction = new int[pattern.length()];
        int j = 0;
        for (int i = 1; i < pattern.length(); i++) {
            //如果下一个字符不属于公共前后缀，就需要从上一个公共前后缀的公共前后缀开始找
            while (j > 0 && pattern.charAt(j) != pattern.charAt(i)) {
                j = prefixFunction[j - 1];
            }
            //如果下一个字符属于公共前后缀，就继续往后找
            if (pattern.charAt(j) == pattern.charAt(i)) {
                j++;
            }
            prefixFunction[i] = j;
        }
        return prefixFunction;
    }
 
例如：模式串ababaca中
i = 4时 ababa 最长公共前后缀 j =3
i = 5时 ababac  j=4时字符串为b i=5字符串为c，最长公共前后缀不能延长了，需要回退计算：
abab
abac
上一个最长公共前后缀是aba，由上观察可知最佳匹配开始路径就是aba的最长公共前后缀a
匹配
ab
ac
结果是不匹配,j=0,继续循环

KMP核心算法实现逻辑如下：

设匹配到文本串的m索引处失败，此时：文本串索引m，模式串索引k=5

     m
ababadeabcababaca
ababaca
     k = 5

根据以上展示的跳跃信息进行跳跃，文本串索引不变，模式串中匹配值ababa，模式串索引=公共最长前后缀长度=3，比较m处('d')和k处('b')字符，发现不匹配，如果匹配则m=m+1,k=k+1，继续进行匹配。

     m
ababadeabcababaca
  ababaca
     k = 3

继续下一次匹配和跳跃，文本串索引不变，模式串中匹配值aba，模式串索引=公共最长前后缀长度=1，比较m处('d')和k处('b')字符，发现不匹配。

     m
ababadeabcababaca
    ababaca
     k = 1

继续下一次匹配跳跃，文本串索引不变，模式串中匹配值1，模式串索引=公共最长前后缀长度=0，比较m处('d')和k处('a')字符，发现不匹配。

     m
ababadeabcababaca
     ababaca
     k = 0

继续下一次匹配，只要k==0，文本串索引就+1继续匹配：

      m = m + 1
ababadeabcababaca
      ababaca
      k = 0

后续循环以上逻辑即可求得结果，代码如下：

    public int KMP(String text, String pattern) {
        int[] prefixFunction = computePrefixFunction(pattern);
        int j = 0;
        for (int i = 0; i < text.length(); i++) {
            while (j > 0 && pattern.charAt(j) != text.charAt(i)) {
                j = prefixFunction[j - 1];
            }
            if (pattern.charAt(j) == text.charAt(i)) {
                j++;
            }
            if (j == pattern.length()) {
                return i - j + 1;  // 返回匹配的起始位置
            }
        }
        return -1;  // 如果没有找到匹配，返回-1
    }