kmp是为了解决什么问题？
字符串匹配问题，用来在主字符串中查找匹配字符串的位置
N, M ：字符串的长度char s[N], p[M]：待匹配串 匹配串eg: s[N] = “ababa”, p[M] = “aba”判断 s[N] 中是否有p[M]这个子串，如果有，开始下标为多少?
解决方法
暴力算法
for(int i = 1; i <= n; i++) { bool flag = true; for(int j = 1; j <= m；j++) { if(s[i+j-1] != p[j]) { flag = false; break; } } }
时间复杂度：O(n*m)
kmp优化
对于模式串中已经匹配过的那些字符，如果我们能找到一些规律，将模式串多往后移动几位，而不是像暴力算法算法一样，每次把模式串移动一位，就可以提高算法的效率。kmp算法给我们提供的思路是：对于模式串，将每一个字符在匹配失败时可以向后移动的最大距离保存在一个next数组。这样当匹配失败时就可以按照next数组中保存的数字向后多移动几位。从而提高算法的效率。
在讲述之前，我们先摆出两个概念：
前缀：指的是字符串的子串中从原串最前面开始的子串，如abcdef的前缀有：a,ab,abc,abcd,abcde
后缀：指的是字符串的子串中在原串结尾处结尾的子串，如abcdef的后缀有：f,ef,def,cdef,bcdef
什么是前缀数组next[]
在KMP算法中有个关键的数组，叫做前缀数组，每一个子串有一个固定的next数组，它记录着字符串匹配过程中失败情况下可以向后多跳几个字符，其实也是子串的前缀和后缀相同的最长长度。
怎么求这个数组我们放在最后说，先说怎么使用这个前缀数组来实现kmp算法
算法思路
思路其实已经说过了，就是在暴力的算法的基础上，在匹配失败的时候往后多跳几位，而跳几位保存在前缀数组中。接下来我们看一下原理是什么样的，为什么前缀数组就可以作为跳几步的依据。举个例子，下图中已经写好了总串s和模式串p,模式串的前缀数组为[0,0,1,2,3],且所以下标都是从1开始。看图中当i=8，j=4时s[i] != p[j + 1]，即将要匹配失败了，图中红色圈住的是子串的后缀。黄圈圈住的是前缀。蓝色圈圈住的是已经和后缀匹配过的部分，那么下一次将模式串后移prefix[j]=2位时，原来的前缀正好对着蓝色圈圈部分，因为前缀=后缀=蓝色圈圈部分，所以移动后的橙色部分就不用再判断了。
再用上一个双指针算法思路。i遍历总串s，j遍历模式串p，判断s[i] 和 p[j + 1]是否匹配。不匹配就将j重置为前缀数组中prefix[j]的值。匹配的话j忘后移动一位。当匹配了n个字符后即代表完全匹配。此时答案即为i-n，如果要继续搜索，要将j再置为prefix[j]。
为了方便写代码所有数组的下标都从1开始
// kmp匹配 for (int i = 1, j = 0; i <= m; i++) { while (j != 0 && s[i] != p[j + 1]) { j = prefix[j]; // s[i] != p[j + 1]即不匹配，则往后移动 } if (s[i] == p[j + 1]) j++; // 匹配时将j++进行下一个字符的匹配 if (j == n) { j = prefix[j]; // 完全匹配后继续搜索 System.out.print(i - n + " "); } }
怎么求前缀数组
前缀数组是kmp里面最难的部分，网上也有很多种求法。比如利用后一个元素和前面的元素之间存在数学公式关系来求，我们这里使用的方式是和上面的匹配过程类似的方法，也就是将前缀看作模式串，在p中匹配他。也就是字符串p自己找自己的匹配串。
完整代码
import java.io.*; public class Main { static int N=100010; static int M=1000010; static char []p=new char[N]; static int []ne=new int[N]; static char []s=new char[M]; public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); int n=Integer.parseInt(br.readLine()); String s1= br.readLine(); for (int i = 1; i <=n; i++) { p[i]=s1.charAt(i-1); } int m=Integer.parseInt(br.readLine()); String s2= br.readLine(); for (int i =1; i <=m; i++) { s[i]=s2.charAt(i-1); } //构建前缀数组ne[] for(int i=2,j=0;i<=n;i++){ while (j!=0 && p[i]!=p[j+1]) j=ne[j]; if(p[i]==p[j+1]) j++; ne[i]=j; } //kmp匹配 for(int i=1,j=0;i<=m;i++){ while (j!=0 && s[i]!=p[j+1]) j=ne[j]; // 匹配时将j++进行下一个字符得匹配 if(s[i]==p[j+1]) j++; if(j==n){ //当匹配成功时继续往下匹配 j=ne[j]; bw.write(i-n+" "); } } bw.flush(); br.close(); bw.close(); } }
