记录编号	453264	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2000] 最长公共子串	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.158 s
提交时间	2017-09-21 09:26:28	内存使用	14.09 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;

inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int read(void) { 
    register int res = 0;
    register char tmp = getc();
    while(!isdigit(tmp)) tmp = getc();
    while(isdigit(tmp))
        res = ((res + (res << 2)) << 1) + (tmp ^ 0x30),
        tmp = getc();
    return res;
}

inline unsigned read(char *s) { 
    register char *p = s;
    while(!islower(*p = getc()));
    while(islower(*(++p) = getc()));
    *p = '\0'; 
    return p - s;
}

typedef unsigned long long ULL;
#define INF (0x7fffffff)

inline bool check(unsigned length);

char s[5][2010];
ULL h[5][2010], xp[2010], hash[5][2010], seed;
unsigned len[5], mxlen, milen = INF;
int N;

int main() { 
#ifndef LOCAL
    freopen("pow.in", "r", stdin);
    freopen("pow.out", "w", stdout);
#endif
    srand(time(NULL));
    N = read(), seed = rand() % 200;
    for(int i = 0; i < N; ++i) { 
        len[i] = read(s[i]);
        milen = min(milen, len[i]);
        mxlen = max(mxlen, len[i]);
        for(int j = len[i] - 1; ~j; --j) 
            h[i][j] = h[i][j+1] * seed + s[i][j];
    }
    if(N == 1) { 
        printf("%d\n", len[0]);
        return 0;
    }
    *xp = 1;
    for(unsigned i = 1; i <= mxlen; ++i) 
        xp[i] = xp[i-1] * seed;
    register unsigned l = 0, r = milen, ans, M;
    while(l <= r) { 
        M = (l + r) >> 1;
        if(check(M))
            ans = M, l = M + 1;
        else r = M - 1;
    }
    printf("%d\n", ans);
}

inline bool check(unsigned length) { 
    register ULL p = xp[length], ph, q;
    for(unsigned i = 0, j = *len - length; i <= j; ++i) 
        hash[0][i] = h[0][i] - h[0][i+length] * p;
    for(int k = 1; k < N; ++k) { 
        for(unsigned i = 0, j = len[k] - length; i <= j; ++i)
            hash[k][i] = h[k][i] - h[k][i+length] * p;
        sort(hash[k], hash[k] + len[k] - length + 1);
    }
    for(unsigned k = 0, t = len[0]-length; k <= t; ++k) { 
        ph = hash[0][k];
        bool flag = true;
        for(int i = 1; i < N; ++i) 
            if(!flag) break;
            else { 
                q = lower_bound(hash[i], hash[i]+len[i]-length+1, ph)-hash[i];
                if(q <= len[i]-length && ph == hash[i][q]) continue;
                flag = false;
            }
        if(flag) return true;
    }
    return false;
}