#include <bits/stdc++.h>
#define MAX 100005
using namespace std;
typedef long long ll;
char W[MAX],T[MAX];
int nxt[MAX];
void getnext(
int lenW)
{
int i=
0,j=-
1;
nxt[i]=-
1;
while(i<
lenW) {
if(j==-
1||W[i]==
W[j]) {
nxt[++i]=++
j;
}
else j=
nxt[j];
}
}
int kmp(
int pos,
int lenW,
int lenT)
{
int i=pos,j=
0,ans=
0;
while(i<
lenT) {
if(T[i]==W[j]||j==-
1) ++i,++
j;
else j=
nxt[j];
if(j==
lenW) {
ans++
;
j=nxt[j-
1];
i--
;
}
}
return ans;
}
int main()
{
scanf(" %s",T);
int lenT=strlen(T);
//长串
scanf(
" %s",W);
int lenW=strlen(W);
//短串
getnext(lenW);
//短串匹配
printf(
"%d\n",kmp(
0,lenW,lenT));
//连续子串个数
return 0;
}
转载于:https://www.cnblogs.com/yzm10/p/9502334.html
相关资源：数据结构—成绩单生成器
