KMP 算法

KMP算法用来计算字串的位置。例如计算s1:abcdef中s2:cde字串的位置。 常规的暴力求解方案下，最多需要给s1中的每一个字符匹配s2.length次，才能得到具体的结果。假设s1.length = m,s2.length = n，则暴力求解的时间复杂度为**O(m *n)**。

KMP算法原理

最长前后缀匹配长度

前缀字符串：
以字符串第一个字符开头的连续字符串，不能包括字符串整体。例如abc的前缀字符串有： a和ab。
后缀字符串
以字符串最后一个字符为结尾的连续字符串，不能包括字符串整体。例如abc的后缀字符串有：bc和c。
最长前后缀匹配长度
即当前缀字串和后缀字串相同的时候，前缀字串的最大长度。例如abcdeabc的最长前后缀匹配长度为3。

KMP过程解析

从S1中求S2的位置：
image.png
从0一致匹配到12，发现a和s不匹配了。 这个时候如果是常规的暴力解法，就会从s1的1开始重新对整个s2进行匹配，如果所示：
image.png
但是在KMP算法中，会根据最大前后缀匹配长度来决定重新匹配的位置，在下图中，KMP算法使得直接从s1的6开始重新进行s2的匹配，同时由于最大前后缀匹配长度的存在，可以确定s2的0-5与s1的6-11是完全相同的，所以直接比较的是s2的6与s1的13。
image.png
可以明显地发现：KMP算法在暴力解法的基础上进行了大幅度的优化。

为什么从s1的6从新开始匹配:

KMP算法的前提是：假设s1和s2从0->m一直是匹配的，此时s2的最大前后缀匹配和为k，那么在s1的0->m-k-1范围内一定没有可以与s2成功匹配的答案（可以证明）。使得只能从**m-k**开始匹配新的答案。
image.png

计算最长前后缀匹配和数组next[]

在KMP算法中，首先需要计算子字符串的最长前后缀匹配和数组，然后根据这个数据来执行KMP算法。最长前后缀匹配数组的计算是一个动态规划的过程，即当前缀后一位和后缀后一位相等的时候，对应的next[index]就增加。
next[i]指的是s2中0->i-1字符串中的最大前后缀匹配和，和当前的第**i**位置无关。所以next[0]由于前面没有字符串，指定为-1。而next[1]由于前面只有一个字符，无法构成前后缀，所以指定为0。

  1. public static int[] getNextArray(char[] s) {
  2.     if (s.length ==1) {
  3.         return new int[]{-1}; 
  4.     }
  5.     int[] next = new int[s.length];
  6.     //指定初始值
  7.     next[0] = -1;
  8.     next[1] = 0; 
  9.     a b b s t k a b b s t k s 
  10.     //s索引
  11.     int index = 2;
  12.     //当前位置的最大前后缀匹配和，也是前缀的后一位的索引
  13.     int cnum = 0; 
  14.     while (index < s.length) {
  15.         //前一位置的前缀后一位 和 后缀的后一位是否相等
  16.         if (s[index-1] == s[cnum]) {
  17.             //相等的话，就更新
  18.             next[index++] = ++cnum; 
  19.         } else if (cnum > 0) {
  20.             //如果不相等的情况下cnum>0，就继续往前跳，找到上一个前缀的最
  21.             //大前后缀匹配和(要匹配的位置)
  22.             cnum = next[cnum];
  23.         } else {
  24.             next[index++] = 0;
  25.         }
  26.     }
  27.    return next; 
  28. }

KMP

  1. public static int kmp(String str1,String str2) {
  2.     if (str1==null || str2==null || str1.length()<str2.length() || str2.length()<1) {
  3.         return -1;
  4.     }
  5.     char[] s1 = str1.toCharArray();
  6.     char[] s2 = str2.toCharArray();
  7.     //str1的索引
  8.     int i1 = 0;
  9.     //str2的索引
  10.     int i2 = 0;
  11.     //计算子字符串的next数组，从而得到下一个要匹配的位置
  12.     int[] next = getNextArray(s2);
  13.     while (i1<s1.length && i2<s2.length) {
  14.         //如果匹配，就都++
  15.         if (s1[i1] == s2[i2]) {
  16.             //即使i2==0了，如果s2[i2]==s1[i1]，那两者直接++
  17.             i1++;
  18.             i2++;
  19.         } else if (next[i2] == 0) {
  20.             //说明当前的i2==0即s2的头字符 != s1[i1],那就只能i1++了
  21.             i1++;
  22.         } else {
  23.             //匹配到现在不相等了，就跳到前缀的后一个位置next[i2]
  24.             i2 = next[i2];
  25.         }
  26.     }
  27.     //如果i2越界了，就说明找到了结果，反之则无解
  28.     return i2==s2.length? i1-i2 : -1; 
  29. }

KMP的时间复杂度

求next数组的时间复杂度为O(length2),KMP的时间复杂度为O(length1)，所以**KMP**算法的时间复杂度为**O(length1)**。