记录编号	414140	评测结果	AAA
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.503 s
提交时间	2017-06-13 15:21:12	内存使用	9.07 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define sc(a) scanf("%d",&a)
#define for1(a,b,i) for(int i=a;i<=b;i++)
#define ll unsigned long long
#define pp 97
const int M=10010;
int t,leni,lena,ans; 
char p[M],s[100*M]; 
ll ha[M],has[100*M],ycl[M];
inline void init(){
       ycl[0]=1;
       for1(1,M-10,i)
         ycl[i]=ycl[i-1]*pp;
}
inline ll getlen(int l,int r){
       ll ans;
       return ans=has[l]-has[r]*ycl[leni];
}
int main()
{
    freopen("oulipo.in","r",stdin);
    freopen("oulipo.out","w",stdout);
    init();
    sc(t);
    while(t--){
      ans=0;
      memset(has,0,sizeof(has));
      memset(ha,0,sizeof(ha));
      scanf("%s%s",p,s);
      leni=strlen(p);lena=strlen(s);
      for(int i=leni-1;i>=0;i--)
         ha[i]=(ha[i+1]*pp)+p[i]-'A';
      for(int i=lena-1;i>=0;i--)
         has[i]=(has[i+1]*pp)+s[i]-'A';
      for(int i=0;;i++){
        if(i+leni>lena)
           break;
        if(ha[0]==getlen(i,i+leni))
          ans++;
      }
      printf("%d\n",ans);
    }
    //while(1);
    return 0;
}