书接上回。过掉了 LCS1。然后这个题 T 了。

#include <cstdio>
#include <cstring>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define M1 1000000007
#define M2 1000000093
using namespace std;
char s[12][100050];
int n, m, b, L, R, l[12];
long long H1[12][100050], H2[12][100050], P1[100050], P2[100050];
inline long long H(int x, int y) {return (1ll * x) << 32 | y;}
inline int A(int x, int y, int mod) {return (x += y) >= mod ? (x - mod) : (x);}
bool C(int k)
{
	__gnu_pbds::gp_hash_table<long long, int> c[12];
	for(int i = 1;i <= n;++i)
		if(i != b) for(int j = k;j <= l[i];++j)
			++c[i][H(A(H1[i][j], M1 - H1[i][j - k] * P1[k] % M1, M1), A(H2[i][j], M2 - H2[i][j - k] * P2[k] % M2, M2))];
	for(int j = k, q;j <= l[b];++j)
	{
		q = 0;
		for(int i = 1;i <= n;++i) if(i != b) 
			q += c[i].find(H(A(H1[b][j], M1 - H1[b][j - k] * P1[k] % M1, M1), A(H2[b][j], M2 - H2[b][j - k] * P2[k] % M2, M2))) != c[i].end();
		if(q == n - 1) return 1;
	}
	return 0;
}
int main()
{
	l[0] = 1e9;
	for(int i = P1[0] = P2[0] = 1;i <= 100000;++i)
		P1[i] = P1[i - 1] * 233 % M1, P2[i] = P2[i - 1] * 233 % M2;
	while(~scanf("%s", s[++n] + 1))
	{
		if((l[n] = strlen(s[n] + 1)) < l[b]) b = n;for(int j = 1;j <= l[n];++j)
			H1[n][j] = (H1[n][j - 1] * 233 + s[n][j]) % M1, H2[n][j] = (H2[n][j - 1] * 233 + s[n][j]) % M2;
	}
	--n;R = l[b];while(L <= R)
	{if(C(m = L + R >> 1)) L = m + 1;else R = m - 1;}
	printf("%d", R);return 0;
}