SCU

Censor

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

She has a long text $p$

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$

( $1 \leq length of w, p \leq 5 \cdot 10^{6}$

Output

For each test, write $1$

Sample Input

    abc
    aaabcbc
    b
    bbb
    abc
    ab

Sample Output

    a
    
    ab


这题用KMP可以写 但是KMP不会

但是用HASH暴力一下，HASH暴力出奇迹

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <queue>
 7 #include <set>
 8 #include <map>
 9 #include <string>
10 #include <math.h>
11 #include <stdlib.h>
12 #include <time.h>
13 using namespace std;
14 typedef unsigned long long ull;
15 const int maxn = 5e6 + 10;
16 const int seed = 13331;
17 ull HASH, s[maxn], p[maxn];
18 char a[maxn], b[maxn], ans[maxn];
19 void init() {
20     p[0] = 1;
21     for (int i = 1 ; i < maxn ; i++)
22         p[i] = p[i - 1] * seed;
23 }
24 int main() {
25     init();
26     while(scanf("%s%s", a, b ) != EOF  ) {
27         int lena = strlen(a), lenb = strlen(b);
28         if (lena > lenb) {
29             printf("%s
", b);
30             continue;
31         }
32         HASH = 0;
33         for (int i = 0 ; i < lena ; i++)
34             HASH = HASH * seed + a[i];
35         int top = 0;
36         s[0] = 0;
37         for (int i = 0 ; i < lenb ; i++) {
38             ans[top++] = b[i];
39             s[top] = s[top - 1] * seed + b[i];
40             if ( top >= lena && s[top] - s[top - lena]*p[lena] == HASH ) top -= lena;
41         }
42         for (int i = 0 ; i < top ; i++)
43             printf("%c", ans[i]);
44         printf("
");
45     }
46     return 0;
47 }