Description：

给很多字符串，求他们的最长公共子串。

$1\leqslant n\leqslant 1000,1\leqslant|S_i|\leqslant 100,\Sigma=\R$

Solution：

写完 $Description$ 发现好像是 $SAM$ 裸题。

写的后缀数组，先二分一个长度，然后把所有 $height<mid$ 的位置截断分成好多块，然后统计一下是不是每一块里都有 $n$ 种字符串，这个可以用一个桶来记录，每到一个截断的位置就把前面那一段的影响清空，注意细节。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 1010

#define MAXM 110

#define MAXL (MAXN * MAXM)

int len[MAXN];

int str[MAXN][MAXM];

int s[MAXN * MAXM],tot = 0;

int rnk[MAXL],sa[MAXL],t1[MAXL],t2[MAXL],c[MAXL],height[MAXL],id[MAXL];

void make_SA(int n,int m)

{

	int *x = t1,*y = t2;

	int p;

	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;

	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 && s[i + k] == s[j + k])++k;

		height[rnk[i]] = k;

	}

	return;

}

int cnt[MAXN],sum = 0;

bool check(int k)

{

	memset(cnt,0,sizeof(cnt));

	int last = 1;

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

	{

		if(height[i] < k)

		{

			for(int j = last;j < i;++j)

			{

				cnt[id[sa[j]]] = 0;

			}

			sum = 0;

			last = i;

			cnt[id[sa[i]]] = 1;

			sum = 1;

		}

		else

		{

			if(cnt[id[sa[i]]] == 0)++sum;

			++cnt[id[sa[i]]];

			if(sum == n)return true;

		}

	}

	return false;

}

int main()

{

	scanf("%d",&n);

	int maxv = 0,minv = 0x3f3f3f3f;

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

	{

		scanf("%d",&len[i]);

		for(int j = 1;j <= len[i];++j)

		{

			scanf("%d",&str[i][j]);

			maxv = max(maxv,str[i][j]);

		}

	}

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

	{

		for(int j = len[i];j >= 2;--j)

		{

			str[i][j] = str[i][j] - str[i][j - 1];

		}

		for(int j = 2;j <= len[i];++j)

		{

			s[++tot] = str[i][j];

			minv = min(minv,s[tot]);

		}

		s[++tot] = ++maxv;

		for(int j = len[i - 1] + 1;j <= len[i - 1] + len[i];++j)id[j] = i;

		len[i] += len[i - 1];

	}

	for(int i = 1;i <= tot;++i)s[i] = s[i] - minv + 1;

	//for(int i = 1;i <= tot;++i)cout << s[i] << " " << id[i] << endl;

	maxv = maxv - minv + 1;

	make_SA(tot,maxv);

	int l = 0,r = tot,mid;

	while(l < r)

	{

		mid = ((l + r + 1) >> 1);

		if(check(mid))l = mid;

		else r = mid - 1;

	}

	cout << l + 1 << endl;

	return 0;

}