poj2774（最长公共子串）

poj2774

题意

求两个字符串的最长公共子串

分析

论文

将两个字符串合并，中间插入分隔符，在找最大的 height 值的时候保证，两个字符串后缀的起始点分别来自原来的两个字符串。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 2e5 + 10;
char s[MAXN], s2[MAXN];
int sa[MAXN], t[MAXN], t2[MAXN], c[MAXN], n; // n 为 字符串长度 + 1，s[n - 1] = 0

int rnk[MAXN], height[MAXN];
// 构造字符串 s 的后缀数组。每个字符值必须为 0 ~ m-1
void build_sa(int m) {
    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 getHeight() {
    int i, j, k = 0;
    for(i = 0; i < n; i++) rnk[sa[i]] = i;
    for(i = 0; i < n - 1; i++) {
        if(k) k--;
        j = sa[rnk[i] - 1];
        while(s[i + k] == s[j + k]) k++;
        height[rnk[i]] = k;
    }
}
void debug() {
    scanf("%s", s);
    n = strlen(s) + 1;
    build_sa(128);
    getHeight();
    for(int i = 1; i < n; i++) printf("%d ", sa[i]); puts("");
    for(int i = 2; i < n; i++) printf("%d ", height[i]);
    // a b a a b
    // 2 3 0 4 1 : aab ab abaab b baab
    //   1 2 0 1
}

// 后缀数组是“排第几的是谁？”，名次数组是“你排第几？”

// 保证 s[n-1] = 0　且前面非 0 //　也就是说空串在最前

// sa[0] = n - 1，sa[i] 有效的只有 [1, n-1] （ 因为前面的 n 加 1 了 ）表示第 i 位的是谁（ 以第几个字符开始的字符串后缀 ）
// height[i] 有效的只有 [2, n-1] 表示 lcp(sa[i], sa[i-1]) 最长公共前缀

int main() {
    scanf("%s%s", s, s2);
    int l1 = strlen(s), l2 = strlen(s2);
    s[l1++] = '#';
    for(int i = l1; i < l1 + l2; i++) s[i] = s2[i - l1];
    n = strlen(s) + 1; // 最后一位留空
    build_sa(128);
    getHeight();
    int ans = 0;
    for(int i = 2; i < n; i++) {
        if(height[i] > ans && ((sa[i] < l1) != (sa[i - 1] < l1)))
            ans = height[i];
    }
    printf("%d
", ans);
    return 0;
}