Link

点击打开ural题目链接

Mean

找出两个字符串的最长公共字串

Analyse

由于两个字符串A,B太长了,所以kmp、hash之类的n2算法肯定是不行了。于是用后缀数组,是O(n×logn),可以解决问题。具体做法就是求出height数组后,检测是不是分别是A,B的后缀,然后利用RMQ求出AB两个串的最长公共前缀即可。

C++ Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 210000;
char buf[maxn];

struct SuffixArray {
    int n, sa[maxn], rank[maxn], height[maxn], t[maxn], t2[maxn], c[maxn];
    char *s;

    SuffixArray() { clear(); }
    void setDate(char *str, int len) { s = str, n = len; }
    void clear() { n = 0; memset(sa, 0, sizeof(sa)); }

    void build_sa(int m = CHAR_MAX) {
        int i, *x = t, *y = t2;
        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(int k = 1; k <= n; k <<= 1) {
            int 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 = 0; 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;
        }
    }

    void build_height() {
        int i, k = 0;
        for(i = 0; i < n; i++) rank[sa[i]] = i;
        for(i = 0; i < n; i++) {
            if(k) k--;
            int j = sa[rank[i]-1];
            while(s[i+k] == s[j+k]) k++;
            height[rank[i]] = k;
        }
    }
}sa;

struct RMQ {
    int d[maxn][30];
    void init(const int *A, int n) {
        for(int i = 0; i < n; ++i) d[i][0] = A[i];
        for(int j = 1; (1<<j) <= n; ++j)
            for(int i = 0; i + (1<<j) - 1 < n; ++i)
                d[i][j] = min(d[i][j-1], d[i+(1<<(j-1))][j-1]);
    }
    int quert(int L, int R) {
        int k = 0;
        while((1<<(k+1)) <= R-L+1) ++k;
        return min(d[L][k], d[R-(1<<k)+1][k]);
    }
}rmq;


int main() {
    int n; scanf("%d", &n);
    scanf("%s %s", buf, buf+n+1);
    buf[n] = buf[2*n+1] = '$'; buf[2*n+2] = NULL;
    sa.setDate(buf, 2*n+2);
    sa.build_sa();
    sa.build_height();
    rmq.init(sa.height, 2*n+2);
    int st = 0, ok = 0;
    int pos1 = 0, pos2 = 0;
    for(int i = 2; i < 2*n+2; ++i) {
        int pos = sa.sa[i];
        if(pos > n) {
            if(pos1) {
                int cur = min(2*n+2-pos, rmq.quert(pos1+1, i));
                if(cur > ok) st = pos, ok = cur;
            }
            pos2 = i;
        } else {
            if(pos2) {
                int cur = min(n-pos, rmq.quert(pos2+1, i));
                if(cur > ok) st = pos, ok = cur;
            }
            pos1 = i;
        }
    }
    for(int i = 0; i < ok; ++i)
        putchar(buf[st+i]);
    putchar('\n');
    return 0;
}

欢迎留言