2015弱校联盟(1) - C. Censor(新Hash板子

Censor

frog is now a editor to censor so-called sensitive words (敏感词).

She has a long text p . Her job is relatively simple -- just to find the first occurence of sensitive word w and remove it.

frog repeats over and over again. Help her do the tedious work.

Input

The input consists of multiple tests. For each test:

The first line contains 1 string w . The second line contains 1 string p .

(String length of w, p < 5×10^6 , w, p consists of only lowercase letter)

Output

For each test, write string which denotes the censored text.

Sample Input

    abc
    aaabcbc
    b
    bbb
    abc
    ab

Sample Output

    a

    ab

题意：第一个串是模版串，后面一个串是主串。
在主串中删除模版串问最后主串什么样子。
做法：用一个数组模拟栈。

//china no.1#include <vector>#include <iostream>#include <string>#include <map>#include <stack>#include <cstring>#include <queue>#include <list>#include <stdio.h>#include <set>#include <algorithm>#include <cstdlib>#include <cmath>#include <iomanip>#include <cctype>#include <sstream>#include <functional>#include <stdlib.h>#include <time.h>#include <bitset>using namespace std;#define LL long longtypedef unsigned long long ULL;const int N = 5e6 + 7;const ULL seed = 1e9 + 13;char w[N], P[N], ans[N];int lw, lp;ULL p[N] = {1ull}, st[N];ULL gethash(char s[], int len){    ULL hashval = 0ull;    for (int i = 0; i < len; ++i)        hashval = hashval * seed + s[i];    return hashval;}int main(void){    int i;    for (i = 1; i < N; ++i)        p[i] = p[i - 1] * seed;    while (~scanf("%s%s", w, P))    {        lw = strlen(w);        lp = strlen(P);        ULL tar = gethash(w, lw);        int top = 0;        st[top] = 0;        for (i = 0; i < lp; ++i)        {            ans[top++] = P[i];            st[top] = st[top - 1] * seed + P[i];            if (top >= lw && st[top] - st[top - lw]*p[lw] == tar)                top -= lw;        }        ans[top] = '\0';        printf("%s\n", ans);    }    return 0;}