记录编号	379758	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2000] 最长公共子串	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.178 s
提交时间	2017-03-07 16:26:37	内存使用	16.66 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cctype>
#include <vector>
using namespace std;
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char readc(){
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
  }
  inline int readint(){
    char c; int r;
    while(c = readc()){if(c >= '0' && c <= '9'){r = c^0x30;break;}}
    while(isdigit(c = readc()))r = (r<<3)+(r<<1)+(c^0x30);
    return r;
  }
  inline int read_string(char *str){
    int len = 1;char c;
    while(!isalpha(c = readc()));str[0] = c;
    while(isalpha(c = readc()))str[len++] = c;
    str[len] = 0;
    return len;
  }
};using IO::read_string; using IO::readint;
const int x = 31;
typedef unsigned long long ULL;
#define MAXN 100002
ULL xp[MAXN];
ULL ha[10][MAXN], hv[10][MAXN];
int len[10];
char str[MAXN];
int n;
bool check(int m){
  for(int i = 0; i < n; i++){ 
    for(int j = 0; j <= len[i]-m; j++)
      hv[i][j] = ha[i][j]-ha[i][j+m]*xp[m];
    if(i)sort(hv[i], hv[i]+len[i]-m+1);
  }
  for(int i = 0; i <= len[0]-m; i++){
    ULL val = hv[0][i];
    int cnt = 1;
    for(int j = 1; j < n; j++){
      ULL *p = lower_bound(hv[j], hv[j]+len[j]-m+1, val);
      if(*p == val)cnt++;
    }
    if(cnt == n)return true;
  }
  return false;
}
int main(){
  //freopen("test_data.txt", "r", stdin);
  freopen("pow.in", "r", stdin);
  freopen("pow.out", "w", stdout);
 // n = readint();
  scanf("%d", &n);
  xp[0] = 1;
  for(int i = 1; i <= MAXN; i++)xp[i] = xp[i-1]*x;
  int minlen = 1e9;
  for(int i = 0; i < n; i++){
    scanf("%s", str);
    //minlen = min(minlen, len[i] = read_string(str));
    minlen = min(minlen, len[i] = strlen(str));
    ha[i][len[i]] = 0;
    for(int j = len[i]-1; ~j; j--)ha[i][j] = ha[i][j+1]*x + str[j];
  }
  int l = 0, r = minlen;
  int ans = 0;
  while(l <= r){
    int m = (l+r)>>1;
    if(check(m))ans = m, l = m+1;
    else r = m-1;
  }
  printf("%d\n", ans);
  return 0;
}