文章目录

• 前言
• 一、KMP算法思想
• • 1.思想
  • 2.next数组
  • 3.kmp函数思路
• 二、代码

前言

最近学到了字符串模块，然后遇到了kmp，之前的哈希一直没看明白黑皮书上的代码，所以打算以后再说。然后就是看了两天的next数组求法，不明白当出现不等情况时为什么j=next[j],在掉了两天头发下，终于搞明白了。

一、KMP算法思想

1.思想

给你两个字符串，一个主串a，一个要匹配的串s

相较于一个一个匹配，一旦遇到不相等字符时主串下一位与副串开头比较，kmp在比较时发现，遇到不同时，指向主串a的指针不需回溯，而是一直走到最后，相反，对于指向副串s的指针j回溯，
模拟：
首先正常比较，发现a!=b情况

正常情况下我们可能会让i=1,j=0,再次遍历比较

但我们不难发现对于s串，他有一个前后缀a
这里我们可以直接移动s而不改变i，减少比较回溯次数

再如
遇到不匹配，但对于s有前后缀相等情况



综上，我们每次只需记录副串s前后缀的位置，就可以知道我们j应该如何回溯了，这边就是next数组

2.next数组

从上面的模拟过程可以看出，next数组主要就是求副串s的最长相同前后缀，
下面是在哔站上找到的感觉最简单的代码，

对于一个字符串s，我们找的是指向s的指针j之前的串中前后缀相等的个数，例如

对于next[5] ( j从1开始)，前缀ab==后缀ab，所以next[5]=2+1;
以下是粗略的求一个串的next数组的过程

（具体文字思路在代码中）

3.kmp函数思路

我们只需每次遇到不匹配的时候，让j回溯到next[j]位即可，其余时候相等则i++;j++;当最终的指针j大小超过副串的长度的时候，说明匹配成功，返回匹配的开始位置即可

二、代码

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;


char a[1005];
char s[1005];

int getNext(char s[],int next[]) {
	int len=strlen(s);
//	int len=s.lengh();
	next[1]=0;
	int j=0;
	int i=1;
	while(i<len) {
		if(j==0||s[i]==s[j]) next[++i]=++j;//先i自增后再指向i位，i++; next[i]=++j
		// 而next[i++]是先指向i位，再对i自增  next[i]=++j; i++;
		else j=next[j];  //回溯到j位之前的前缀位置 然后在进行比较
		                 //为什么回溯到1-j前缀的位置
	                	 //因为对于1-i位前缀和后缀是一样的，而对于前缀的前缀（即1-j位的前缀）
		                 //同样也是后缀的前缀，
		                //前缀的前缀=前缀的后缀
		                //后缀=前缀
		                //后缀的前缀=后缀的后缀   =   前缀的前缀=前缀的后缀
		                //所以前缀(即j位前的前缀next[j])=i位的后缀,
		                //回溯到s[i]==s[j]，此时，j前面的必定对于i前面的有相等的字符
		                //因为前i项找到了前缀，
		                //相当于一直缩小前缀的长度，找到符合的一项
	}

}

void kmp(char a[],char s[]) {
	int next[1005];

	int alen=strlen(a);
	int slen=strlen(s);
	getNext(s,next);
	int res=0;
	int i=0,j=0;

	while(i<alen&&j<slen){

		if(a[i]==s[j]){
			i++;
			j++;
		}
		else {
			j=next[j];
		}
	}
	if(j>=slen){
		cout<<i-slen<<endl;
	}
}
int main() {
	while(cin>>a>>s) {
		kmp(a,s);
	}
}