题目大意

从左到右依次把两个单词合并成一个单词。

合并两个单词的时候，要找到最大的i (i≥0)i \ (i≥0)，满足第一个单词的长度为 ii 的后缀和第二个单词长度为 ii 的前缀相等，然后把第二个单词第 ii 位以后的部分接到第一个单词后面

请你输出最后合并后的单词。

分析

字符串 hash

对于答案串 resres ，其后缀暴力枚举匹配 s[i]s[i] 的前缀

Code

字符串hash字符串hash from 严格鸽

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
const int maxn = 1000005;
using ull = unsigned long long;
string res;

struct str_hash{
    ull base = 131;
    ull p[maxn];
    char s[maxn];
    unordered_map<ull,ull> hs;
    ull n;

    void init(string &str){
        n = str.size();
        hs.clear();
        for(int i = 1;i <= n;i++) s[i] = str[i-1];  // 转化成 下标从1开始的字符串
        p[0] = 1;
        for(int i = 1;i <= n;i++){
            hs[i] = hs[i-1]*base+s[i];
            p[i] = p[i-1] * base;
        }
    }

    void add(string str){
        for(auto c:str){
            int i = ++n;
            hs[i] = hs[i-1]*base+c;
            p[i] = p[i-1]*base;
        }
    }

    ull hash(int l,int r) {
        return hs[r] - hs[l-1]*p[r-l+1];
    }
    ull pre(int i){
        return hash(1,i);
    }
    ull suf(int i){
        return hash(n-i+1,n);
    }
}o,p;


signed main()
{
    int n;cin>>n;
    vector<string> s(n+1);
    forr(i,1,n) cin >> s[i];
    res = s[1];
    o.init(res);
    forr(i,2,n){
        p.init(s[i]);
        int len = min(o.n,(ull)s[i].size());
        int j = 0;
        for(int k = 1;k <= len;k++){
            if(o.suf(k) == p.pre(k))
                j = k;
        }
        //cout << i <<" "<< j << endl;
        string t = s[i].substr(j);
        o.add(t);
        res += t;
    } 
    cout << res << endl;
    return 0;
}