POJ 2774 Long Long Message

后缀数组论文题，也是后缀数组的入门题——最长公共子串。
另外这题是双倍经验 HDU 1403 Longest Common Substring不过HDU的数据更水一点。

题意：
给你两个字符串，求最长公共子串。

思路：
因为是论文题，我不可能讲的比论文还详细的啦……这不是显然的吗

看了论文后基本就是套板子，因为它已经吧最关键的地方给证明了，然后有一个小地方，为什么可以直接拿 sa 数组与第一个字符串长度 key 比较呢？
那是因为，sa数组本身就是记录后缀排名第 idx 位的是哪一个后缀，而后缀和第一个字符串 key ，都是从左往右正向计数的。故可以直接拿来比较。

AC Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int maxn = 2e5 + 10;
int sa[maxn];
int rnk[maxn], height[maxn];

void buildSA(int s[], int n, int m)
{
    int t1[maxn], t2[maxn], buc[maxn];
    int p, *x = t1, *y = t2;
    each(i, m) buc[i] = 0;
    each(i, n) buc[x[i] = s[i]]++;
    range(i, 1, m - 1) buc[i] += buc[i - 1];
    reach(i, n) sa[--buc[x[i]]] = i;
    for (int k = 1; k <= n; k <<= 1) {
        p = 0;
        range(i, n - k, n - 1) y[p++] = i;
        each(i, n) if (sa[i] >= k) y[p++] = sa[i] - k;
        each(i, m) buc[i] = 0;
        each(i, n) buc[x[i]]++;
        range(i, 1, m - 1) buc[i] += buc[i - 1];
        reach(i, n) sa[--buc[x[y[i]]]] = y[i];
        swap(x, y);
        p = 1, x[sa[0]] = 0;
        range(i, 1, n - 1) 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 s[], int n)
{
    int j, k = 0;
    each(i, n + 1) rnk[sa[i]] = i;
    each(i, n)
    {
        k ? k-- : 0;
        j = sa[rnk[i] - 1];
        while (s[i + k] == s[j + k])
            k++;
        height[rnk[i]] = k;
    }
}

char str[maxn];
int s[maxn], slen[maxn];

int main()
{
    while (scanf("%s", str) != EOF) {
        int len = strlen(str), key = len;
        str[len] = '$';
        scanf("%s", str + len + 1);
        len = strlen(str);
        each(i, len+1) s[i] = str[i];
        buildSA(s, len + 1, 128);
        getHeight(s, len);
        int ans = 0;
        range(i, 2, len) if ((sa[i] < key) + (sa[i - 1] < key) == 1) ans = max(ans, height[i]);
        printf("%d\n", ans);
    }
    return 0;
}