记录编号	333827	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2000] 最长公共子串	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	0.057 s
提交时间	2016-10-31 15:42:03	内存使用	19.61 MiB

#pragma warning(disable: 4786)
#define pro __attribute__((optimize("O3")))
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring> 

using namespace std;

#define Rep(_i,x,y) for(int (_i)=(x);(_i)<=(y);(_i)++)
typedef long long lg;
typedef unsigned long long ulg; 
//////////////////////////////////////////////
//        读入,输出优化(int,long long)
namespace PROIO {
#define getc() (*ptr++) 
char cha[20000000],*ptr=cha;
template <class T>
  pro inline void read(T &x) {
	 register bool flag = 0;register char c;
	 while((c=getc())>'9'||c<'0')
	   if(c == '-') flag = 1;
	 x = c-'0';
	 while((c=getc())<='9'&&c>='0')
	  x = ((x<<1)+(x<<3))+c-'0';
	 if(flag) x = -x;  
   }

template <class T>
  pro inline void write(register T x) {    
    if(x < 0) {
        putchar('-');  
        x = -x;  
    }  
    if(x >= 10)    
        write(x/10);
    putchar(x%10+'0');    
   }    
}
using namespace PROIO; 
///////////////////////////////////////////////

//  #define TEST

///////////////////////////////////////////////
//      hash_table模版
#ifdef TEST
#define mod 1000007
struct hash_table {
	int val;
	hash_table():val(0){}
	hash_table(int val):val(val){}
};

vector<hash_table> tab[mod];

pro unsigned int f(int x) {
	return ((unsigned int)(7*(x-5)+x*31))%mod;
}

pro void insert_h(register int v) {
	tab[f(v)].push_back(v);
}

pro bool query_h(register int x) {
	unsigned int tmp = f(x);
	for (int i = 0; i < tab[tmp].size(); i++)
	 if(tab[tmp][i].val == x)
	  return true;
	return false;
}
/* work为 codevs 2147 数星星*/
pro void work() {
	fread(ptr,1,20000000,stdin);
	int n;lg x;
	read(n);
	for (int i = 1;i <= n; i++) {
		read(x);
		if(query_h(x)) putchar('1');
		else putchar('0'),insert_h(x);
	}
}
///////////////////////////////////////////////
//          字符串hash模版 
#else
#define base 31
#define MAXX 2100

ulg b[MAXX];

struct String_hash {
	char s[MAXX];int len,st;
	ulg Hash[MAXX],h[MAXX];
    pro inline ulg gethash(int l,int r) {
	   return Hash[r]-Hash[l-1]*b[r-l+1];
    }
    pro void BKDRHash()  {
       for (int i = 1; i <= len; i++)
        Hash[i] = Hash[i-1] * base + s[i-1];  
    }
    pro void make(register int x) {
//cout<<len<<endl;
    	for(int i = 1;i <= len-x+1; i++) 
    	 h[i] = gethash(i,i+x-1);
    	sort(h+1,h+len-x+2);st = 1;
	}
}a[6];

pro inline void init() {
	b[0] = 1;
	for (int i = 1; i < MAXX; i++)
	  b[i] = b[i-1]*base;
}

/**/
static int n;

pro bool pd(int x) {
	Rep(i,1,n) 
		a[i].make(x);
	for (int i = 1; i <= a[1].len-x+1; i++) {
	  register bool ok = 1;
	  for (int j = 2; j <= n; j++) {
	  	while(a[j].h[a[j].st] < a[1].h[i] && a[j].st <= a[j].len)
		  a[j].st++;
		if(a[j].st > a[j].len) return false;
		if(a[j].h[a[j].st] != a[1].h[i]) {
			ok = 0; continue;
		} 
	  }
	  if(ok) return true; 
	}
	return false;
}

#define mid (l+r)>>1
pro void f(int l,int r) {
	if(r-l <= 1) printf("%d",pd(r) ? r:l);
	else pd(mid) ? f(mid,r):f(l,mid);
}

pro void work() {
	freopen("pow.in","r",stdin);
	freopen("pow.out","w",stdout);
    init();
    scanf("%d",&n);
    int maxx = 3000;
    for (int i = 1; i <= n; i++) {
    	scanf("%s",a[i].s);
		a[i].len = strlen(a[i].s);
		maxx = min(maxx,a[i].len); 
    	a[i].BKDRHash();
	}
	f(0,maxx);
}
#undef base
////////////////////////////////////////////
#endif

pro int main() {
	work();
    return 0;
}