HDU 6208 The Dominator of Strings 后缀自动机

The Dominator of Strings 后缀自动机

HDU 6208 The Dominator of Strings

My Solution

题意：每组数据给出n个字符串，每组总共最多1e5个字符，然后要求判断，其中是否存在一个字符串，而其它字符串是这个字符串的子串。总共有30MB的输入。

贪心+后缀自动机

如果用AC自动机来做很可能会TLE，但后缀自动机在这里相对不容易被卡掉，首先我们多出了一个贪心优化，那就是那个可能存在的母串必定是长度最长的字符串，如果长度最长的字符串不止一个，则它们必定是完全相同的，所以后缀自动机只会用最长的那个字符串来建立自动机，而如果是AC自动机则必须使用全部的字符串来建立自动机，加上乘个memset[26]很容易被卡掉，如果非要卡后缀自动机可以把这30MB的输入数据都处理为每组数据2个字符串，一个长度为1e5-1一个长度为1，这样每次都要用最长串来建立自动机，所以复杂度为O(26*30M) == 7.8e8，在加上sam来做常数很小，所以这里要卡后缀自动机相对麻烦写，然后写了一发后缀自动机就过了。

首先找出最长的一个字符串建立后缀自动机，然后由于sam存放的是所以的后缀，然后后缀的前缀就是子串，所以只要对剩下的n-1个字符串分别从sam的0节点开始向下跑即可，如果能跑完就说是母串的某个后缀的前缀。

时间复杂度 O(n)

空间复杂度 O(2*n*26)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 2*1e5 + 8;

string s;
struct SAM{
    int ch[MAXN][26], pre[MAXN], val[MAXN];
    int last, tot, minl[MAXN], maxl[MAXN];
    void init(){
        last = tot = 0;
        memset(ch[0], -1, sizeof ch[0]);
        pre[0] = -1; val[0] = 0;
        minl[0] = maxl[0] = 0;
    }
    void extend(int c){
        int p = last, np = ++tot;
        val[np] = val[p] + 1;
        memset(ch[np], -1, sizeof ch[np]);
        minl[np] = maxl[np] = val[np];
        while(~p && ch[p][c] == -1) ch[p][c] = np, p = pre[p];
        if(p == -1) pre[np] = 0;
        else{
            int q = ch[p][c];
            if(val[q] != val[p] + 1){
                int nq = ++tot;
                memcpy(ch[nq], ch[q], sizeof ch[q]);
                val[nq] = val[p] + 1;
                minl[nq] = maxl[nq] = val[nq];
                pre[nq] = pre[q];
                pre[q] = pre[np] = nq;
                while(~p && ch[p][c] == q) ch[p][c] = nq, p = pre[p];
            }
            else pre[np] = q;
        }
        last = np;
    }
    bool _find(const string &s){
        int sz = s.size(), u = 0, c, i;
        for(i = 0; i < sz; i++){ c = s[i] - 'a'; if(~ch[u][c]) u = ch[u][c]; else{ return false; } } return true; } } sam; string str[MAXN]; int main() { #ifdef LOCAL freopen("a.txt", "r", stdin); //freopen("a.out", "w", stdout); #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int T, n, sz, i, len, ind; bool ans; cin >> T;
    while(T--){
        cin >> n;
        len = 0;
        for(i = 0; i < n; i++){ cin >> str[i];
            if(len < str[i].size()){
                len = str[i].size();
                ind = i;
            }
        }
        s.clear();
        s += str[ind];
        sz = s.size();
        sam.init();
        for(i = 0; i < sz; i++) sam.extend(s[i] - 'a');
        ans = true;
        for(i = 0; i < n; i++){
            if(i == ind) continue;
            if(!sam._find(str[i])){
                ans = false;
                break;
            }
        }
        if(ans) cout << str[ind] << "n";
        else cout << "Non";
    }
    return 0;
}