数据结构——kmp字符串

kmp字符串

kmp是一种高效存储字符串匹配的算法
简单来说就是给定一个模式（母）串S，以及一个模板（子）串P
求出模板（子）串P在模式（母）串S中所有出现的位置的起始下标。

当然你也可以暴力的去做，但是不如看看kmp的想法吧
遇到两个字符不匹配的情况时，希望可以多跳几个字符，减少比较次数
KMP算法的思想是：

• 在模式串和主串匹配过程中，当遇到不匹配的字符时，对于主串和模式串中已对比过相同的前缀字符串，找到长度最长的相等前缀串，从而将模式串一次性滑动多位，并省略一些比较过程。

看下图理解什么是比较前缀，一次滑动多位


可能还不清楚、来看一个例子吧

看我的图可能都要看晕了，来看具体的题目吧

题目

给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串P在模式串S中多次作为子串出现。
求出模板串P在模式串S中所有出现的位置的起始下标。

题解

模板

	private static final int N = 100010; //p 模板串
	private static final int M = 1000010;// s 被匹配的母串
	private static char[] p = new char[N];
	private static char[] s = new char[M];
	private static int[] next = new int[N];//最关键的next数组
	//1. next数组初始化
		for(int i=2,j=0;i<=n;i++){
			//从2开始是 next[1]默认为0
			while(j!=0&&p[i]!=p[j+1]){
				j = next[j];
			}		
			if(p[i]==p[j+1]){
				j++;
			}		
			next[i] = j;
		}
		
		//System.out.println(Arrays.toString(next));
		
		//2. 匹配过程
		for(int i=1,j=0;i<=m;i++){
			while(j!=0&&s[i]!=p[j+1]){
				j = next[j];
			}
			
			if(s[i]==p[j+1]){
				j++;
			}
			
			if(j==n){
				//本来应该是i-n+1,但是我们是从1开始存储的
				// a b c d
				//   b c d
				// 1 2 3 4   j=3=n  i=4 位置i-n+1 2但是我们应改返回1
				bw.write(i-n+" ");
				j = next[j];
			}
		}