功能

• 在主串中查找子串，返回头位置(0开头索引)

复杂度

• 
• n,m为主串和子串长度

思路

• 把主串和子串拼接到一起，中间隔开，记为合并串s
• 对s中的每一个子串计算其最长匹配真前后缀长度，如果有某一个字串的最长匹配真前后缀长度等于子串长度，则说明查找到子串
• 对于每一个子串希望求他的最长匹配真前后缀长度，他的最长匹配前后缀长度等于他去掉末尾的子串s'匹配上的长度

代码

void kmp(string &s1,string &s2){
	int m=s2.size();
	s2=s2+'#'+s1;
	int n=s2.size();
	vector<int>p(n);
	for(int i=1;i<n;i++){
		int len =p[i-1];
		while(len&&s2[i]!=s2[len]){
			len=p[len-1];
		}//找第一个能匹配上最后一位的子串
		if(s2[i]==s2[len]){
			p[i]=len+1;//找到了就更新len
			if(p[i]==m){
				return i-m*2+1;//去除偏移量
			}
		}
	}
	return -1;
}

视频讲解