果断吃果果....
不解释...
#include<iostream>
using namespace std;char s[1111111],t[11111];
int next[11111],lenS,lenT;
int cnt;
void setNext()
{int j=0,k=-1;next[0]=-1;while( j<lenT ){if( k==-1||t[j]==t[k] )next[++j]=++k;elsek=next[k];}
}void kmp( int start )
{int i=start,j=0;cnt=0;while( i<lenS&&j<lenT ){if( j==-1 || s[i]==t[j] )i++,j++;elsej=next[j];if( j==lenT )cnt++,j=next[j];}
}int main()
{int T;scanf( "%d",&T );while( T-- ){scanf( "%s%s",&t,&s );lenS=strlen(s);lenT=strlen(t);setNext();kmp(0);printf( "%d\n",cnt );}return 0;
}