POJ 2217: Secretary

蟻本ツアーです。これ KMP(table を作る部分) で解けそうですがせっかくなので suffix array で解きました。

問題

2217 -- Secretary

解法

S += T とやって２つの文字を合体させた後, lcp テーブルを作ります。で, S の前半側と S の後半側で一致する文字数を lcp で調べます。

const int MAXN = 20010;
namespace SA {
    int rank[MAXN], tmp[MAXN];
    int n, k;
    bool compare_sa(int i, int j) {
        if (rank[i] != rank[j]) return rank[i] < rank[j];
        int ri = (i+k <= n) ? rank[i+k] : -1;
        int rj = (j+k <= n) ? rank[j+k] : -1;
        return ri < rj;
    }
    // suffix array を構築する
    // O(N log^2 N)
    // how to use: construct_saを呼ぶとsa配列にSuffixArrayを構築する
    void createSA(const string& s, int* sa) {
        n = s.size();
        // 最初は 1 文字ソート
        for (int i = 0; i <= n; i++) {
            sa[i] = i;
            rank[i] = i < n ? s[i] : -1;
        }
        for (k = 1; k <= n; k*=2) {
            sort(sa, sa+n+1, compare_sa);
            tmp[sa[0]] = 0;
            for (int i = 1; i <= n; i++) {
                tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i]) ? 1 : 0);
            }
            for (int i = 0; i <= n; i++) rank[i] = tmp[i];
        }
    }
    namespace LCP {
        int rank[MAXN];
        // suffix array の情報をもとに longest common prefix を構築する
        // O(N)
        // hot to use: construct_lcpに文字列と suffix array の情報を入れると lcp 配列を作る
        void createLCP(const string& s, const int* sa, int* lcp) {
            int n = s.size();
            for (int i = 0; i <= n; i++) rank[sa[i]] = i;
            int h = 0;
            lcp[0] = 0;
            for (int i = 0; i < n; i++) {
                int j = sa[rank[i]-1];
                h = max(0, h-1);
                for (; j+h < n && i+h < n; h++) {
                    if (s[j+h] != s[i+h]) break;
                }
                lcp[rank[i]-1] = h;
            }
        }
    } // namespace LCP
} // namespace SA

char str[MAXN];

void getInput(string& s) {
    fgets(str, MAXN, stdin);
    strtok(str, "\n\0");
    s = str;
}

int sa[MAXN], lcp[MAXN];

int main() {
    int T;
    scanf("%d\n", &T);
    while (T--) {
        string S, T;
        getInput(S); getInput(T);
        int n = S.size(), m = T.size();
        S += '\n';
        S += T;
        SA::createSA(S, sa);
        SA::LCP::createLCP(S, sa, lcp);
        int nm = S.size(), ans = 0;
        for (int i = 0; i < nm; i++) {
            if (sa[i] < n && sa[i+1] < n) continue;
            if (sa[i] > n && sa[i+1] > n) continue;
            ans = max(ans, lcp[i]);
        }
        printf("Nejdelsi spolecny retezec ma delku %d.\n", ans);
    }
    return 0;
}