记录编号	491123	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2000] 最长公共子串	最终得分	100
用户昵称	胡嘉兴	是否通过	通过
代码语言	C++	运行时间	4.022 s
提交时间	2018-03-14 20:04:40	内存使用	6.71 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+7, inf = 1e9;
int n, m = 127;
char s[N];
vector<int> vec;
int sa[N], tp[N], tax[N], rak[N], book[N], height[N], st[N][20];
void pr(int* a, int n)
{
    for(int i = 1; i <= n; i++)
    {
        printf("%d ", a[i]);
    }
    puts("");
}
void distribution_sort()
{
    for(int i = 0; i <= m; i++)
    {
        tax[i] = 0;
    }
    for(int i = 1; i <= n; i++)
    {
        tax[rak[i]]++;
    }
    for(int i = 1; i <= m; i++)
    {
        tax[i] += tax[i-1];
    }
    for(int i = n; i >= 1; i--)
    {
        sa[tax[rak[tp[i]]]--] = tp[i];
    }
    return;
}
void SA()
{
    for(int i = 1; i <= n; i++)
    {
        tp[i] = i;
        rak[i] = s[i];
    }
    distribution_sort();
    for(int k = 1, p = 1; k <= n&&p < n; k <<= 1, m = p)
    {
        p = 0;
        for(int i = 1; i <= k; i++)
        {
            tp[++p] = n-k+i;
        }
        for(int i = 1; i <= n; i++)
        {
            if(sa[i]>k)
            {
                tp[++p] = sa[i]-k;
            }
        }
        distribution_sort();
        swap(rak, tp);
        rak[sa[1]] = p = 1;
        for(int i = 2; i <= n; i++)
        {
            rak[sa[i]] = (tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+k]==tp[sa[i]+k]) ? p : ++p;
        }
    }
    return;
}
void get_height()
{
    int k = 0;
    for(int i = 1; i <= n; i++)
    {
        rak[sa[i]] = i;
    }
    for(int i = 1; i <= n; i++)
    {
        if(rak[i]==1)
        {
            continue;
        }
        if(k)
        {
            k--;
        }
        int j = sa[rak[i]-1];
        while(j+k<=n&&i+k<=n&&s[i+k]==s[j+k]&&book[i]==book[i+k]&&book[j]==book[j+k])
        {
            k++;
        }
        height[rak[i]] = k;
    }
    return;
}
int query(int l, int r)
{
    if(l>r)
    {
        swap(l, r);
    }
    l++;
    int k = 0, ret;
    while((1<<(k+1))<=r-l+1)
    {
        k++;
    }
    return min(st[l][k], st[r-(1<<k)+1][k]);
}
int main()
{
    int t, ans = 0;
    freopen("pow.in","r",stdin);
    freopen("pow.out","w",stdout);
    scanf("%d", &t);
    vec.push_back(0);
    for(int i = 0; i < t; i++)
    {
        scanf("%s", s+1+n);
        int tmp = strlen(s+1);
        for(int j = n+1; j <= tmp; j++)
        {
            book[j] = tmp;
        }
        n = tmp;
        vec.push_back(n);
    }
	SA();
	get_height();
	for(int i = 1; i <= n; i++)
    {
        st[i][0] = height[i];
    }
    for(int j = 1; (1<<j) <= n; j++)
    {
        for(int i = 1; i + (1<<j) <= n; i++)
        {
            st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
        }
    }
    for(int i = 1; i <= vec[1]; i++)
    {
        int cnt = inf;
        for(int j = 2; j < vec.size(); j++)
        {
            int cur = 0;
            for(int k = vec[j-1]+1; k <= vec[j]; k++)
            {
                cur = max(cur, query(rak[i], rak[k]));
            }
            cnt = min(cnt, cur);
        }
        ans = max(ans, cnt);
    }
    printf("%d\n", ans);
	return 0;
}