KMP板子题;
如果不会可以参考其他算法书
代码:
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<cstring>
using namespace std;
string s1,s2;
int len1,len2;
int f[];
int main(){
cin>>s1>>s2;
len1=s1.size(),len2=s2.size();
f[]=f[]=;
for(int i=;i<len2;i++){
int j=f[i];
while(j&&s2[i]!=s2[j]) j=f[j];
if(s2[i]==s2[j]) f[i+]=j+;
else f[i+]=;
}
int j=;
for(int i=;i<=len1;i++){
while(j&&s1[i]!=s2[j]) j=f[j];
if(s1[i]==s2[j]) j++;
if(j==len2) {printf("%d",i-j+);break;}
}
return ;
}