BZOJ-3942: [Usaco2015 Feb]Censoring

Description

有一个S串和一个T串，长度均小于1,000,000，设当前串为U串，然后从前往后枚举S串一个字符一个字符往U串里添加，若U串后缀为T，则去掉这个后缀继续流程。

维护一个栈，维护栈顶lenp个字符的hash值。
据说？？？双乘数 unsigned long long 自然溢出hash效果不错的样子。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
char s[1001000],p[1001000]; 
ull has1,has2;
ull haz1[1001000],haz2[1001000];
char z[1001000];
ull pow1,pow2;
ull Pow(ull x,ull y)
{
    ull re=1;
    while(y)
    {
        if(y&1) re*=x;
        x*=x; y>>=1;
    }
    return re;
}
int main()
{
    scanf("%s%s",s,p);
    int lens=strlen(s),lenp=strlen(p);
    for(int i=0;i!=lenp;++i)
    {
        has1=has1*233+p[i]-'a';
        has2=has2*2333+p[i]-'a';
    }
    pow1=Pow(233,lenp);
    pow2=Pow(2333,lenp);
    int top=0;
    for(int i=0;i!=lens;++i)
    {
        z[++top]=s[i];
        haz1[top]=haz1[top-1]*233+s[i]-'a';
        haz2[top]=haz2[top-1]*2333+s[i]-'a';
        if(top>lenp) haz1[top]-=pow1*(z[top-lenp]-'a'),haz2[top]-=pow2*(z[top-lenp]-'a');
        if(top>=lenp&&haz1[top]==has1&&haz2[top]==has2) top-=lenp;
    }
    z[++top]='\0'; printf("%s",z+1);
    return 0;
}