kmp：寻找最长子串（次数和位置）

const int N=2;
int lenw,lent;
char w[10000+2],t[1000000+2];int nex[10000+2],f[1000000+2];
inline void before()
{
for(register int i=2,j=0;i<=lenw;++i)
{
while(j>0&&w[j+1]!=w[i])j=nex[j];
if(w[j+1]==w[i])nex[i]=++j;
else nex[i]=j;
// chu("nex[%d]:%d\n",i,nex[i]);
}
}
inline void deal()
{
for(register int i=1,j=0;i<=lent;++i)
{
while(j>0&&(w[j+1]!=t[i])||j==lent)j=nex[j];
if(w[j+1]==t[i])//意义：看在w[j]和t[i-1]匹配的情况下w[J+1]和t[i]的匹配情况
{
f[i]=++j;
}
else f[i]=j;
// chu("f[%d]:%d\n",i,f[i]);
}
}
int T;
int main()
{
// freopen("exam.txt","r",stdin);
T=re();
//chu("T:%d\n",T);
while(T--)
{
scanf("%s%s",w+1,t+1);
lenw=strlen(w+1),lent=strlen(t+1);
before();

deal();int ans=0;
_f(i,lenw,lent)
{
if(f[i]==lenw)++ans;
}

chu("%d\n",ans);
}
return 0;
}