POJ 3261. Milk Patterns

http://vjudge.net/problem/viewProblem.action?id=10375

Brief description:

。。求最長 k-重複子串
。。也就是 max{lcp(l, r) | r-l = k}

Analysis:

非常經典的例題。

演算法一:字元串哈希(70ms
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1563261

演算法二:SA + LCP(40ms
http://vjudge.net/problem/viewSource.action?id=2604648

演算法三:SA + 二分(40ms
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1563212

演算法四:SA + 單調隊列(30ms
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1563242

——————————

「看到這題 SAM 做不了直接傻眼了囧。。。 」 —— http://yc5-yc.blog.163.com/blog/static/137797109201441910522414/

演算法五:SAM + MAP(400ms++

http://vjudge.net/problem/viewSource.action?id=2604642

(卧槽數據要不要這麼弱。。(直接開 26 居然 秒 A 了。。。。
http://vjudge.net/problem/viewSource.action?id=2604640

SPOJ 7258. Lexicographical Substring Search

http://vjudge.net/problem/viewProblem.action?id=28015

Brief description:

求給定字元串,字典序第 kth 大的子串(重複的算一個)。

Analysis:

演算法一:後綴數組
預處理前 i 個後綴能形成多少個不同的子串,之後二分,複雜度 $O(logn)$。
http://vjudge.net/problem/viewSource.action?id=1577464

演算法二:後綴自動機
DP 出每個狀態出發可以識別多少子串。之後在 SAM 上,逐個字元嘗試。
。。。這種方法時間複雜度較差(依賴於子串長度)、想要通過此題需要常數優化和一定運氣。。。
http://vjudge.net/problem/viewSource.action?id=2604504

Codechef April Challenge 2012. Substrings on a Tree

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