2017-12-06 22:18:30

1 1 1 1 4 然后答案是2？

#include <cstring>
#include <cstdio>
#include <cctype>
#include <map>
using namespace std;
#define MAXN 1010
#define MAXM 2000020
#define INF 0x3f3f3f3f
inline char get_char(){
static char buf[500001], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 500000, stdin), p1 == p2) ? EOF : *p1 ++;
}
int num = 0;
char c;
while (isspace(c = get_char()));
while (num = num * 10 + c - 48, isdigit(c = get_char()));
return num;
}
inline int upmax(int &a, const int &b){
if(a < b) a = b;
return a;
}
int n, m[MAXN], s[MAXN][MAXN], size[MAXM];
namespace SAM{
int cnt = 1, lst = 1;
map<int, int> son[MAXM];
int pre[MAXM], step[MAXM];
inline void Insert(int tar){
int p = lst, np = ++cnt;
for(lst = np, step[np] = step[p] + 1;p && !son[p][tar]; p = pre[p]) son[p][tar] = np;
if(!p) pre[np] = 1;
else {
int q = son[p][tar];
if(step[p] + 1 == step[q]) pre[np] = q;
else {
int nq = ++cnt;
step[nq] = step[p] + 1;
son[nq] = son[q];
for(pre[nq] = pre[q], pre[q] = pre[np] = nq; son[p][tar] == q; p = pre[p]) son[p][tar] = nq;
}
}
}
}
int vis[MAXM];
inline int Get_Ans(){
int ret = 1;
for(int i = 1; i <= n; i++){
int p = 1, *tp = s[i];
for(int j = 2; j <= m[i]; j++){
p = SAM::son[p][tp[j] - tp[j - 1]];
int tmp = p;
while(vis[tmp] != i){
vis[tmp] = i;
size[tmp]++;
tmp = SAM::pre[tmp];
}
}
}
for(int i = 1; i <= SAM::cnt; i++)
if(size[i] == n)
upmax(ret, SAM::step[i] + 1);
return ret;
}
int main(){
for(int i = 1; i <= n; i++){