HDU 6138 Fleet of the Eternal Throne 后缀数组+字典树

Fleet of the Eternal Throne 后缀数组+字典树

Source

2017 Multi-University Training Contest - Team 8

HDU 6138

My Solution

题意：给出n(n<=1e5)个字符串，且字符串的字符总和<=1e5，给出m个询问，每次给定x，y，找出对于给定str[x]和str[y]
的公共子串且满足这个串是所有串中的某个串的前缀，要求所得的公共串的长度尽可能大。

后缀数组+字典树

首先用给出的n个字符串建立字典树，

然后对于每次的询问，把str[x]和str[y]用‘#’连起来然后跑出后缀数组，

对于所有的ind[i](其中sa[ind[i]] <= len， ind[i]为其在sa数组中的下标)，然后对于 ind[i] - ind[i-1] > 1则说明ind[i]和ind[i-1]直接存在!(sa[j] <= len)的情况，此时的height[ind[i]]表示

他们的后缀的最大相同后缀也就是 str[x]与str[y]的一个子串，然后用字典树O(length)的跑出护符条件的最大长度。

同理对于所有的ind'[i](其中sa[ind[i]] >= len)也跑一遍，记录最大值，就是答案了。

时间复杂度 O(nlogn)

空间复杂度 O(sum_length)

#include 
#include 
#include 
#include 
#include 
#include 






using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 8;
const int CHAR_SIZE = 26;
const int MAX_SIZE = 1e5 + 8;

struct AC_Machine{//这里只使用了字典树的功能，由于方便直接上了AC自动机的SCL
    int ch[MAX_SIZE][CHAR_SIZE];//, danger[MAX_SIZE], fail[MAX_SIZE];
    int sz, n, u, c;
    void init(){
        sz = 1;
        memset(ch[0], 0, sizeof ch[0]);
        //memset(danger, 0, sizeof danger);
    }
    void _insert(const string &s){
        n = s.size();
        u = 0;
        for(int i = 0; i < n; i++){
            c = s[i] - 'a';
            if(!ch[u][c]){
                memset(ch[sz], 0, sizeof ch[sz]);
                //danger[sz] = 0;
                ch[u][c] = sz++;
            }
            u = ch[u][c];
        }
        //danger[u]++;
    }
    int _find(const string &s){
        n = s.size();
        u = 0;
        for(int i = 0; i < n; i++){
            c = s[i] - 'a';
            if(!ch[u][c]){
                return i;
            }
            u = ch[u][c];
        }
        return n;

    }
}ac;

string str[MAXN];

const int maxn = 2e5 + 8;
int sa[maxn], height[maxn];
int _rank[maxn], t1[maxn], t2[maxn], c[maxn];
string s;
inline void get_sa(const int &n, int m)
{
    int i, k, *x = t1, *y = t2, p, j;
    for(i = 0; i < m; i++) c[i] = 0;
    for(i = 0; i < n; i++) ++ c[x[i] = s[i]];
    for(i = 1; i < m; i++) c[i] += c[i - 1]; for(i = n - 1; i >= 0; i--) sa[-- c[x[i]]] = i;
    for(k = 1; k <= n; k <<= 1){
        p = 0;
        for(i = n - k; i < n; i++) y[p ++] = i;
        for(i = 0; i < n; i++) if(sa[i] >= k) y[p ++] = sa[i] - k;
        for(i = 0; i < m; i++) c[i] = 0;
        for(i = 0; i < n; i++) ++ c[x[y[i]]];
        for(i = 1; i < m; i++) c[i] += c[i - 1]; for(i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
        swap(x, y), p = 1, x[sa[0]] = 0;
        for(i = 1; i < n; i++) x[sa[i]] = (y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+k] == y[sa[i]+k]) ? p - 1 : p ++; if(p >= n) break;
        m = p;
    }
    k = 0;
    for(i = 0; i < n; i++) _rank[sa[i]] = i;
    for(i = 0; i < n; i++){
        if(k) --k; if(!_rank[i]) continue;
        j = sa[_rank[i] - 1];
        while(s[i + k] == s[j + k]) k++;
        height[_rank[i]] = k;
    }
}

inline void print(const int &n)
{
    for(int i = 1; i <= n; i++){
        //cout << i << " : " << _rank[sa[i]] << " " << sa[i] << endl;
        for(int j = sa[i]; j < n; j++){
            cout << s[j];
        }
        cout << endl;
    }
    cout << endl; } int xind[MAXN]; int main() { #ifdef LOCAL freopen("f.txt", "r", stdin); //freopen("f.out", "w", stdout); #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int T, n, m, i, j, szs, x, y, len1, last , now, ptr; int l, r, mid, ans; cin >> T;
    while(T--){
        cin >> n;
        ac.init();
        for(i = 1; i <= n; i++){ cin >> str[i];
            ac._insert(str[i]);
        }
        cin >> m;
        while(m--){
            cin >> x >> y;
            s.clear();
            s += str[x];
            s += '#';
            s += str[y];
            szs = s.size();
            get_sa(szs+1, 256);
            len1 = str[x].size();
            last = 0; ans = 0; ptr = 0;
            for(i = 0; i < szs; i++){ if(sa[i] >= len1){
                    xind[ptr] = i;
                    ptr++;
                }
            }
            //print(szs);
            for(i = 1; i < ptr; i++){ if(xind[i] - xind[i-1] > 1){
                    //cout << height[xind[i]] << "?" << endl;
                    if(ans < height[xind[i]]){
                        ans = max(ans, ac._find(s.substr(sa[xind[i]], height[xind[i]])));
                    }
                }
            }
            ptr = 0;
            for(i = 0; i < szs; i++){
                if(sa[i] <= len1){
                    xind[ptr] = i;
                    ptr++;
                }
            }
            //print(szs);
            for(i = 1; i < ptr; i++){ if(xind[i] - xind[i-1] > 1){
                    //cout << height[xind[i]] << "?" << endl;
                    if(ans < height[xind[i]]){
                        ans = max(ans, ac._find(s.substr(sa[xind[i]], height[xind[i]])));
                    }
                }
            }
            cout << ans << "n";
        }

    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

HDU 6138 Fleet of the Eternal Throne 后缀数组+字典树

Fleet of the Eternal Throne 后缀数组+字典树

Source

My Solution

相关推荐

POJ – 3882 Stammering Aliens 后缀数组、二分、二叉堆、ST表

UESTC 1709 DNA序列 AC自动机+dp+矩阵快速幂优化

URAL – 1960 Palindromes and Super Abilities 回文自动机

UESTC 8 God Only Knows! AC自动机

共有 0 条评论

公告

游戏服务器开发 最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发 最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类