字元串哈希 - SCU - 4438 棧維護哈希字首和

題目連結：http://acm.scu.edu.cn/soj/problem.action?id=4438

題目大意：

給定一個字元串A和一個字元串B，如果如果B中存在A字元串，就在B中把A字元串去掉，輸出最後去掉A字元串之後B字元串

用一個棧維護字元，如果棧的倒數|A|個數==B那麼删除這你個數。

繼續添加字元。

根據哈希值的計算公式：（左為高位。相當于p進制的數。）

根據子串哈希值的計算公式：

那麼根據目前棧頂的元素，就能推導下個字元的哈希值。

#include<bits/stdc++.h>

#define ull unsigned long long
using namespace std;
const int maxn=5000006;

ull base =131;
ull g[maxn];
ull p[maxn];

ull Hash(char s[])
{
    int n=strlen(s+1);
    g[0]=0;
    for(int i=1;i<=n;i++)
    {
        g[i]=g[i-1]*base+s[i];
    }
    return g[n];
}

void getp()
{
    p[0]=1;
    for(int i=1;i<=maxn;i++)
    {
        p[i]=p[i-1]*base;
    }
}

ull getLR(int l, int r)//取出T裡l - r裡面的字元串的hash值
{
    return g[r]-g[l-1]*p[r-l+1];
}

char s[5000060], t[5000060], ans[5000060];

int main()
{
    getp();
    while(~scanf("%s%s",s+1,t+1))
    {
        int Ls=strlen(s+1), Lt=strlen(t+1);
        ull key = Hash(s);
        int tot=0;
        for(int i=1;i<=Lt;i++)
        {
            ans[++tot]=t[i];
            g[tot]=g[tot-1]*base+t[i];
            if(tot>=Ls&&g[tot]-g[tot-Ls]*p[Ls]==key)
            {
                tot-=Ls;
            }
        }
        ans[tot+1]=0;
        printf("%s\n",ans+1);
    }

    return 0;
}