Description：

给 $n$ 个字符串，求两两之间最长公共子串。

$1\leqslant n\leqslant 10^6$

Solution：

本题卡空间，因此不能用 $SAM$ ，也不能用 $ST$ 表，把所有字符串接在一起求 $SA$ ，发现最长公共子串一定在字典序相邻两个来自不同子串的地方取得，也就是说答案一定产生在某一个位置和他之前另一个字符串出现的第一个位置，那么我们就可以维护每个字符串上一次出现的位置以及从那个位置到这里的 $height$ 的最小值更新答案即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXN 2000010

int m,n;

char S[MAXN];

int id[MAXN];

char s[MAXN];

int sa[MAXN],rnk[MAXN],height[MAXN];

int c1[MAXN],c2[MAXN];

int c[MAXN];

void make_SA(int n,int m)

{

    int *x = c1,*y = c2;

    for(int i = 1;i <= m;++i)c[i] = 0;

    for(int i = 1;i <= n;++i)++c[x[i] = s[i]];

    for(int i = 1;i <= m;++i)c[i] += c[i - 1];

    for(int i = n;i >= 1;--i)sa[c[x[i]]--] = i;

    int p = 0;

    for(int k = 1;k <= n;k = k << 1)

    {

        p = 0;

        for(int i = n - k + 1;i <= n;++i)y[++p] = i;

        for(int i = 1;i <= n;++i)if(sa[i] > k)y[++p] = sa[i] - k;

        for(int i = 1;i <= m;++i)c[i] = 0;

        for(int i = 1;i <= n;++i)++c[x[y[i]]];

        for(int i = 1;i <= m;++i)c[i] += c[i - 1];

        for(int i = n;i >= 1;--i)sa[c[x[y[i]]]--] = y[i];

        p = 1;

        swap(x,y);

        x[sa[1]] = 1;

        for(int i = 2;i <= n;++i)

        {

            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++p);

        }

        if(p >= n)break;

        m = p;

    }

    for(int i = 1;i <= n;++i)rnk[sa[i]] = i;

    int k = 0;

    for(int i = 1;i <= n;++i)

    {

        if(rnk[i] == 1)continue;

        if(k)--k;

        int j = sa[rnk[i] - 1];

        while(j + k <= n && i + k <= n && s[i + k] == s[j + k])++k;

        height[rnk[i]] = k;

    }

    return;

}

int last[55];

int minh[55];

int ans[55][55];

int main()

{

	scanf("%d",&m);

	int cur = 1;

	n = 0;

	for(int i = 1;i <= m;++i)

	{

		scanf("%s",S + 1);

		int l = strlen(S + 1);

		for(int p = 1;p <= l;++p)

		{

			s[++n] = S[p];

			id[n] = i;

		}

		s[++n] = cur++;

		id[n] = 0;

	}

	make_SA(n,256);

	for(int i = 1;i <= n;++i)

	{

		int p = id[sa[i]];

		last[p] = i;

		minh[p] = 0x3f3f3f3f;

		for(int j = 1;j <= m;++j)

		{

			if(p == j)continue;

			minh[j] = min(minh[j],height[i]);

			ans[p][j] = max(ans[p][j],minh[j]);

		}

	}

	for(int i = 1;i <= m;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			if(i == j)continue;

			printf("%d ",max(ans[i][j],ans[j][i]));

		}

		puts("");

	}

    return 0;

}