题解：P5028 Annihilate

· · 题解

分析

题目要求求出每一对字符串的最长公共子串。

  1. 最长公共子串可以联想到后缀数组中的公式 lcp (sa[i],sa[j]) = \min_{x=i+1}^n height_x。
  2. 经典套路：把所有字符串连在一起处理。
  3. 分隔符不能少，并且要区分。

综合上述想法，可以把所有字符串连在一起（别忘了分隔符），然后求后缀数组。求出 height。求完了以后按照后缀排序的顺序扫一遍，对于每个后缀，枚举所有其他的字符串，求出它们与这个后缀的 lcp，然后更新答案。

计算 lcp 的过程就是一段 height 求最小值的过程。由于空间问题，最好别用数据结构（也没必要）。直接利用贪心的思想，越近越优，所以每一个不同的字符串只需要保存一个目前的 height 最小值就行了，这个值就是最近的，也是所有最小值中最大的。

代码

AC 774 ms，30.5 MB。


// Author: chenly8128
// Created: 2024-12-28 14:12:03

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+1000;
const int MAXM = 256;
namespace SA {
    int sa[MAXN],rk[MAXN],old[MAXN<<1],id[MAXN],cnt[MAXN<<1],cur;
    int height[MAXN];
    void Sort (const char * const s,int n) {
        memset (cnt,0,sizeof (cnt));
        int m = MAXN,p = 0,ct = 255;
        for (int i = 1;i <= n;i++) cnt[rk[i]=(s[i]=='@'?++ct:s[i])]++;
        for (int i = 1;i <= m;i++) cnt[i] += cnt[i-1];
        for (int i = 1;i <= n;i++) sa[cnt[rk[i]]--] = i;
        for (int w = 1;w <= n;w <<= 1,m = p) {
            cur = 0;
            for (int i = n-w+1;i <= n;i++) id[++cur] = i;
            for (int i = 1;i <= n;i++)
                if (sa[i] >= w) id[++cur] = sa[i]-w;
            memset (cnt,0,sizeof (cnt));
            for (int i = 1;i <= n;i++) cnt[rk[i]]++;
            for (int i = 1;i <= m;i++) cnt[i] += cnt[i-1];
            for (int i = cur;i > 0;i--) sa[cnt[rk[id[i]]]--] = id[i];
            memcpy (old,rk,sizeof (rk));
            p = 0;
            for (int i = 1;i <= n;i++)
                if (old[sa[i]] == old[sa[i-1]] && old[sa[i]+w] == old[sa[i-1]+w]) rk[sa[i]] = p;
                else rk[sa[i]] = ++p;
            if (p == n) break;
        }
    }
    void Height (const char * const s,int n) {
        for (int i = 1,k = 0;i <= n;i++) {
            if (rk[i] == 0) continue;
            k = max(0,k-1);
            while (s[i+k] != '@' && s[i+k] == s[sa[rk[i]-1]+k]) k++;
            height[rk[i]] = k;
        }
    }
    void build (const char * const s,int n) {
        Sort(s,n);
        Height(s,n);
    }
}
int n,tmp[55],ne[55],ans[55][55];
string s,p;
int main (void) {
    ios::sync_with_stdio(false);
    cin >> n;
    s = " ";
    for (int i = 1;i <= n;i++) {
        cin >> p;
        s += p;
        s += '@';
        tmp[i] = s.size()-1;
    }
    SA::build(s.c_str(),s.size()-1);
    for (int i = 1;i <= s.size()-1;i++) {
        int w = SA::sa[i],be = n;
        while (be >= 1 && tmp[be-1] >= w) be--;
        for (int j = 1;j <= n;j++) {
            ne[j] = min(ne[j],SA::height[i]);
            if (be != j) ans[be][j] = max(ans[be][j],ne[j]);
        }
        ne[be] = 0x3f3f3f3f;
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++)
            if (i != j) printf ("%d ",max(ans[i][j],ans[j][i]));
        putchar ('\n');
    }
    return 0;
}