记录编号	569256	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2000] 最长公共子串	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.098 s
提交时间	2022-02-27 13:16:35	内存使用	2.23 MiB

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#define OPEN(_x) freopen(#_x".in", "r", stdin); freopen(#_x".out", "w", stdout)
#define ABS(_x) ((_x)<0?(-(_x)):(_x))
#define MAX(_a, _b) ((_a)<(_b)?(_b):(_a))
#define MIN(_a, _b) ((_a)>(_b)?(_b):(_a))
#define fi first
#define se second

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> PII;

namespace IO{
    template<typename T>
    inline T read() {
        T ret=0, sig=1; char ch=0;
        while(ch<'0'||ch>'9') { if(ch=='-') sig=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); }
        return ret*sig;
    }
    template<typename T>
    inline void read(T &x) {
        T ret=0, sig=1; char ch=0;
        while(ch<'0'||ch>'9') { if(ch=='-') sig=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); }
        x = ret*sig;
    }
    template<typename T>
    inline void write(T x) {
        if(x<0) putchar('-'), x=-x;
        T stk[100], tt=0;
        do stk[tt++]=x%10, x/=10; while(x);
        while(tt) putchar(stk[--tt]+'0');
    }
};

const int N = 10010, P = 13331;
int n, lens[10];
char str[N];
ull p[N], a[N], h[10][N], hv[10][N];

void make_hash(char str[], ull ha[]) {
    p[0] = 1;
    int len = strlen(str);
    ha[0] = str[0];
    for(register int i = 1; i<len; ++i) {
        ha[i] = ha[i-1] * P + str[i];
        p[i] = p[i-1] * P;
    }
}

inline ull get(ull ha[], int l, int r) {
    return ha[r] - ha[l-1] * p[r-l+1];
}

bool check(int x) {
    // cout << "case" << ' ' << x << '\n';
    for(register int i = 0; i<n; ++i) {
        for(register int j = 0; j<=lens[i]-x; ++j)
            hv[i][j] = get(h[i], j, j+x); // hv[i][j] 表示第i个字符串从j开始长度为x+1的子串的hash值
        if(i) sort(hv[i], hv[i]+lens[i]-x+1); // 排序以进行二分
    }
    for(register int i = 0; i<=lens[0]-x; ++i) {
        // cout << "* " << i << ' ' << lens[0]-x << " *" << '\n';
        ull val = hv[0][i];
        // cout << "bg: " << i << " val:" << val << '\n';
        int cnt = 1;
        for(register int j = 1; j<n; ++j) {
            ull l = 0, r = lens[j]-x+1; 
            while(l < r) {
                int mid = l+r >>1;
                if(hv[j][mid]>=val) r = mid;
                else l = mid+1;
            }
            // cout << "No." << j+1 << ' ' << "find: " << r << " val: " << hv[j][r] << '\n';
            if(hv[j][r] == val) cnt++;
        }
        // cout << cnt << '\n';
        if(cnt == n) return true;
    }
    return false;
}

int main() {
    #ifdef DEBUG
    OPEN(test);
    #endif
    OPEN(pow);
    IO::read(n);
    int l = 0, r = 0x7fffffff;
    for(register int i = 0; i<n; ++i) {
        scanf("%s", str);
        lens[i] = strlen(str);
        r = MIN(r, lens[i]);
        make_hash(str, h[i]);
    } 
    // 二分答案, 若满足性质, 则ans>=mid
    while(l < r) {
        int mid = l+r+1 >>1;
        // puts("***************");
        if(check(mid-1)) l = mid;
        else r = mid-1;
        // puts("***************\n");
    }
    IO::write(r);
    return 0;
}