思路
模板題碟绑，做的和閱讀題一樣搀军。。
AC代碼
#include<iostream>
using namespace std;
const int MAXN=10000002;
string P;
string T;
int NEXT[MAXN];
int plen,tlen;
void getNEXT(){
int k,j;
k = -1;j = 0;NEXT[0] = -1;
while(j<plen){
if(k==-1||P[k] == P[j]){
NEXT[++j] = ++k;
if(P[j] == P[k]){
NEXT[j] = NEXT[k];
}
}else{
k=NEXT[k];
}
}
}
int KMP_Count(){
int ans = 0;
int i = 0;
int j = 0;
getNEXT();
while(i<tlen){
if(j==-1||T[i] == P[j]){
i++;
j++;
// cout<<"j = "<<j<<endl;
}else
{
j = NEXT[j];
}
if(j == plen){
ans ++;
j = NEXT[j];
}
}
return ans;
}
int KMP_Index()
{
int i = 0, j = 0;
getNEXT();
while(i < tlen && j < plen)
{
if(j == -1 || T[i] == P[j])
{
i++; j++;
}
else
j = NEXT[j];
}
if(j == plen)
return i - plen;
else
return -1;
}
int main(){
ios::sync_with_stdio(false);
int TT;
cin>>TT;
while(TT--){
cin>>P>>T;
tlen = T.length();
plen = P.length();
int ans;
ans=KMP_Count();
cout<<ans<<"\n";
}
return 0;
}
