Brief description:

给定一个 tire，求其中互不相同的子串的个数。之后每次询问，求将 a-z 的优先级重拍后字典序第 kth 大的子串。

Analysis:

广义后缀自动机。注意这个是 12 年的题。。。

修改 Ext() 过程，tail 指针现在需要作为参数传入。。。

    int Ext(int c, int tail){
        int u = tail, uu = new_node(); len[uu] = len[u] + 1;
        while (u && !v) v = uu, u = p;
        if (!u && !v) v = uu, pp = 0;
        else{
            if (len[v] == len[u] + 1) pp = v;
            else{
                int _v = v, vv = new_node(_v); len[vv] = len[u] + 1;
                par[_v] = pp = vv; while (v == _v) v = vv, u = p;
            }
        }
        return uu;
    }

之后。。

    void Init(){

        RD(n, q); RS(s+1); n = strlen(s+1); REP_1(i, n) s[i] -= 'a';

        //RST(hd);
        FOR_C(i, 2, n<<1){
            RD(aa, bb);
            suc[i] = hd[aa], hd[aa] = i++;
            suc[i] = hd[aa], hd[aa] = i;
        }

        tot = 0; queue<int> Q; Q.push(1);
        GtoM[1] = Ext(s[1], new_node());

        while(SZ(Q)){
            int u = Q.front(); Q.pop();
            REP_G(i, u) if (!GtoM[v]){
                GtoM[v] = Ext(s[v], GtoM[u]);
                Q.push(v);
            }
        }
    }

Select 的过程参照 SPOJ SUBLEX 即可。

http://www.codechef.com/viewsolution/4511141

Posted by xiaodao
Category: CodeChef
Tags: 后缀三姐妹