P3375 【模板】KMP字符串匹配

---

思路：

KMP算法的精髓在于，它最大化里利用上了上次匹配上的子串，没有低效率的一位一位为开头去寻找，关键在于匹配上的子串可以决定下次开始寻找的位置。其中利用到的原理则是最长相同前缀后缀长度。比如我们已经寻找到了一个二者匹配的局部相同子串abcefabc,那么下次开始寻找（主串下标不变）的位置这则是这个相同子串abc的第4个e，但是如果局部相同的子串是abcdef的话，则下次开始的位置则从头开始判断。

---

#include<stdio.h>
#include<string.h>
const int N=1e6+8;
char s1[N],s2[N];
int len_s1,len_s2,kmp[N];//kmp代表s2的长度为i时的最长公共前缀后缀 
int main(){
	scanf("%s%s",s1+1,s2+1);
	len_s1=strlen(s1+1),len_s2=strlen(s2+1);
	int j=0;
	for(int i=2;i<=len_s2;i++){
		while(j&&s2[j+1]!=s2[i]){
			j=kmp[j];
		}
		if(s2[j+1]==s2[i]){
			j++;
		}
		kmp[i]=j;
	}
	
	 j=0;
	for(int i=1;i<=len_s1;i++){
		while(j>0&&s2[j+1]!=s1[i]){
			j=kmp[j];
		}
		if(s2[j+1]==s1[i]){
			j++;
		}
		if(j==len_s2){
			printf("%d\n",i-len_s2+1);
		}
	}
	for(int i=1;i<=len_s2;i++){
		printf("%d ",kmp[i]);
	}
	return 0;
}
/*#include<iostream>
#include<cstring>
#define MAXN 1000010
using namespace std;
int kmp[MAXN];//kmp代表当s2的长度为i的时候，此时的前缀（不包含自己）和后缀相同时的最长长度 
int la,lb,j; 
char a[MAXN],b[MAXN];
int main()
{
    cin>>a+1;
    cin>>b+1;
    la=strlen(a+1);
    lb=strlen(b+1);
    for (int i=2;i<=lb;i++)//生成kmp数组，因为i=1的时候不存在真前后缀，故直接跳过 
	   {     
	   while(j&&b[i]!=b[j+1]) //如果前i-1长度的时候最长相同前缀后缀长度不为0，新增的在i-1后面的字符于j后面的字符不相同 
        j=kmp[j];    // 则向前搜索，看看上一次可以符合嘛 
       if(b[j+1]==b[i])j++;  //当j为0的时候，检查b的第一个元素是否和最后一个元素相同，如果相同则j++//j不是0的时候则是检查新增的字符是否等于j后面的字符  
        kmp[i]=j;//保存当前长度最长相同前缀后缀长度 
       }
    j=0;
    for(int i=1;i<=la;i++)
	   {
          while(j>0&&b[j+1]!=a[i]) 
           j=kmp[j];// 
          if (b[j+1]==a[i]) 
           j++;
          if (j==lb) {cout<<i-lb+1<<endl;j=kmp[j];}
       }

    for (int i=1;i<=lb;i++)
    cout<<kmp[i]<<" ";
    return 0;
}*/