Program:
[cpp] #include #include #include #include #include #include #include #define ll long long #define oo 1000000000 using namespace std; char s[2][1000005]; int _next[1000005]; int main() { int T,i,j,k,l0,l1,ans; scanf("%d",&T); while (T--) { scanf("%s%s",s[0]+1,s[1]+1); l0=strlen(s[0]+1); l1=strlen(s[1]+1); memset(_next,0,sizeof(_next)); s[0][l0+1]='#'; for (i=2;i<=l0+1;i++) { k=_next[i-1]; while (k && s[0][k]!=s[0][i-1]) k=_next[k]; _next[i]=k+1; } k=ans=0; for (i=1;i<=l1;i++) { k++; while (k && s[0][k]!=s[1][i]) k=_next[k]; if (k==l0) ans++; } printf("%d\n",ans); } return 0; }