记录编号	270813	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2000] 最长公共子串	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.211 s
提交时间	2016-06-15 11:40:07	内存使用	0.60 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e4 + 1e2;

int n, m, cnt;

#define be(tar, x) (tar <= r[x] and tar >= l[x])
#define same(i, j) (y[sa[i - 1]] == y[sa[i]] and y[sa[i - 1] + j] == y[sa[i] + j])
#define is_ch(x)   (x <= 'z' and x >= 'a')

int sa[maxn], rk[maxn], he[maxn];
int buk[256];
int x[maxn], y[maxn];

int get_line(int *tar) {
	int i = 0;
	char tmp = getchar();
	while(!is_ch(tmp)) tmp = getchar();
	while( is_ch(tmp)) {
		m = max(m, tar[i++] = tmp);
		tmp = getchar();
	}
	return i;
}

int a[maxn];
int l[maxn], r[maxn];
int tot;

void read() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		l[i] = tot;
		tot += get_line(a + tot);	
		r[i] = tot;
		a[tot++] = '#' + i;
	}
	a[tot - 1] = '#';
	tot--;
}

void DA(int len, int top) {

	for(int i = 0; i < top; i++) buk[i] = 0;
	for(int i = 0; i < len; i++) buk[x[i] = a[i]]++;
	for(int i = 1; i < top; i++) buk[i] += buk[i - 1];
	for(int i = len - 1; i >= 0; i--) sa[--buk[x[i]]] = i;
	
	for(int j = 1; j < len; j <<= 1) {
		int p = 0;
		for(int i = len - j; i < len; i++) y[p++] = i;
		for(int i = 0; i < len; i++) if(sa[i] >= j) y[p++] = sa[i] - j;
		
		for(int i = 0; i < top; i++) buk[i] = 0;
		for(int i = 0; i < len; i++) buk[x[y[i]]]++;
		for(int i = 1; i < top; i++) buk[i] += buk[i - 1];
		for(int i = len - 1; i >= 0; i--) sa[--buk[x[y[i]]]] = y[i];
		
		swap(x, y);
		p = 1; x[sa[0]] = 0;
		for(int i = 1; i < len; i++) x[sa[i]] = same(i, j) ? p - 1 : p++;
		if(p >= len) break;
		top = p;
	}
}

void get_rank(int len) {
	for(int i = 0; i <= len; i++) rk[sa[i]] = i;
}

void get_height(int len) {
	int k = 0;
	for(int i = 0; i < len; i++) {
		if(k) k--;
		int j = sa[rk[i] - 1];
		while(a[i + k] == a[j + k]) k++;
		he[rk[i]] = k;
	}
}

bool use[maxn];

int belong(int tar) {
	for(int i = 1; i <= n; i++) {
		if(be(tar, i)) return i;
	}
}

bool judge(int num) {
	int cnt = 0;
	for(int i = 1; i <= tot; i++) {
		cnt = 0;
		memset(use, 0, sizeof(use));
		if(he[i] >= num) {
			int b = belong(sa[i - 1]);
			if(!use[b]) use[b] = true, cnt++;
		}
		while(he[i] >= num and i < tot) {
			int b = belong(sa[i]);
			if(!use[b]) use[b] = true, cnt++;
			i++;
		}
		if(cnt == n) return true;
	}
	return false;
}

void test() {
	for(int i = 1; i <= tot; i++) {
		for(int j = sa[i]; j < tot; j++) {
			printf("%c", a[j]);
		}
		printf("\n");
	}
}


void solve() {
	m = 256;
	DA(tot + 1, m);
//	test();
	get_rank(tot);
	get_height(tot);
	int le = 0, ri = tot+1, mid;
	while(le + 1< ri) {
		mid = (le + ri) >> 1;
		if(judge(mid)) le = mid;
		else ri = mid - 1;
	}
	if(judge(ri)) le = ri;
	printf("%d", le);
}

int main() {
	freopen("pow.in",  "r", stdin);
	freopen("pow.out", "w", stdout);
	read();
	solve();
	return 0;
}