HDU 6208 (字符串hash)

题目链接： http://acm.split.hdu.edu.cn/showproblem.php?pid=6208

题意：给你n个串，能不能在这n个串中找到一个串，使得其它所有的串都是这个串的子串。

题解：找到最长的串作为主串，将主串hash一下，然后去匹配其它串即可

代码：

#pragma GCC diagnostic error "-std=c++11"
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define FIN freopen("in.txt","r",stdin)
#define IO ios_base::sync_with_stdio(0),cin.tie(0)
#define pb push_back
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PIR;

const int MAXN = 1e5+5;

int T, n;
ULL H[MAXN], qpow[MAXN];
string S, s[MAXN];
map <ULL, bool> vis;

void pre () {
    qpow[0] = 1;
    for (int i = 1; i <= 1e5; ++i) qpow[i] = qpow[i-1]*27;
}
ULL getHash (int l, int r) {
    if (l == 0) return H[r];
    else return (H[r]-H[l-1]*qpow[r-l+1]);
}
void solve () {
    H[0] = S[0]-'a'+1;
    for (int i = 1; i < S.size(); ++i) H[i] = H[i-1]*27+S[i]-'a'+1;

    for (int i = 1; i <= n; ++i) {
        if (s[i] == S) continue;
        ULL e = s[i][0]-'a'+1, e1 = S[0]-'a'+1;
        for (int j = 1; j < s[i].size(); ++j) e = e*27+s[i][j]-'a'+1;
        int ok = 0;
        for (int j = 0; j < S.size(); ++j) {
            if (j+s[i].size()-1 >= S.size()) break;
            ULL x = getHash(j, j+s[i].size()-1);
            if (x == e) {
                ok = 1;
                break;
            }
        }
        if (!ok) {
            cout << "No" << endl;
            return ;
        }
    }
    cout << S << endl;
}
int main ()
{IO;
    //FIN;
    pre();
    cin >> T;
    while (T--) {
        vis.clear();
        cin >> n;
        int maxn = 0, id = -1;
        for (int i = 1; i <= n; ++i) {
            cin >> s[i];
            if (s[i].size() > maxn) {
                maxn = s[i].size();
                id = i;
            }
        }
        S = s[id];
        solve();
    }
    return 0;
}