POJ3461一道kmp题，字符串Hash也可

题目链接：http://icpc.njust.edu.cn/Problem/Pku/3461/

代码如下：

 #include<cstdio>

 #include<string.h>

 using namespace std;

 typedef unsigned int ui;

 typedef long long ll;

 typedef unsigned long long ull;

 #define pf printf

 #define mem(a,b) memset(a,b,sizeof(a))

 #define prime1 1e9+7

 #define prime2 1e9+9

 #define pi 3.14159265

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define scand(x) scanf("%llf",&x)

 #define f(i,a,b) for(int i=a;i<=b;i++)

 #define scan(a) scanf("%d",&a)

 #define dbg(args) cout<<#args<<":"<<args<<endl;

 #define inf 0x3f3f3f3f

 #define maxn 1000010

 int n,m,t;

 ull Hash[maxn],h[maxn];

 char a[maxn],b[maxn];

 const int p=;

 void init()

 {

     h[]=;

     f(i,,maxn-)

     {

         h[i]=h[i-]*p;

     }

  }

 int main()

 {

     //freopen("input.txt","r",stdin);

     //freopen("output.txt","w",stdout);

     //std::ios::sync_with_stdio(false);

     scan(t);

     init();

     while(t--)

     {

         scanf("%s%s",&a,&b);

         int lena=strlen(a);

         int lenb=strlen(b);

         int ans=;

         int hasha=a[]-'a',hashb;

         f(i,,lena-)

         {

             hasha=hasha*p+a[i]-'a';

         }

         Hash[]=b[]-'a';

         f(i,,lenb-)

         {

             Hash[i]=Hash[i-]*p+b[i]-'a';

         }

         f(i,,lenb-lena)

         {

             int l=i;

             int r=l+lena-;

             hashb=Hash[r]-Hash[l-]*h[lena];

             if(hasha==hashb)ans++;

         //    dbg(ans);

         }

         pf("%d\n",ans);

     }

  }