BZOJ 4698: Sdoi2008 Sandy的卡片

这道题看到加几个数就能变成另一个数就知道是差分啦，然后显而易见的就是最后的答案为所有串的最长公共串+1，那我们之后怎么办呢，我们先对所有串建一个广义后缀自动机，然后在自动机上搜寻每一个单词，对单词的每一个节点一直跳parent指针，路径上每一个点的次数加一，统计出所有访问次数为字符串总数的长度最大值就好啦，为了不重复访问，我们将每一个点弄一个标记，为了防止繁琐的清空操作，弄一个时间戳就好啦。我这个傻逼一开始还以为只要把开头变成零就不用加一了-_-

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<map>
using namespace std;
struct sam
{map<int,sam*> son;sam* parent;int v;int time_clock;int max_len;sam(int _=0):max_len(_),parent(0x0),v(0){}
}*root=new sam(),*last=root;
int ans=0;
int n;
void my_insert(int x)
{sam *p=last;sam *np=new sam(p->max_len+1);while(p && !p->son[x]){p->son[x]=np;p=p->parent;}if(!p) np->parent=root;else{sam *q=p->son[x];if(q->max_len==p->max_len+1) np->parent=q;else{sam *nq=new sam(p->max_len+1);nq->parent=q->parent;nq->son=q->son;q->parent=nq,np->parent=nq;while(p && p->son[x]==q){p->son[x]=nq;p=p->parent;}}}last=np;
}
int a[1001][1001];
int len[1001];
void my_search()
{for(int i=1;i<=n;i++){sam *o=root;for(int j=1;j<=len[i];j++){int x=a[i][j]-a[i][j-1];if(j!=1){while(o && !o->son[x]) o=o->parent;o=o->son[x];sam *p=o;while(p && p->time_clock!=i){p->v++;if(p->v==n) ans=max(ans,p->max_len);p->time_clock=i;p=p->parent;}}}}
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&len[i]);last=root;for(int j=1;j<=len[i];j++){scanf("%d",&a[i][j]);int x=a[i][j]-a[i][j-1];if(j!=1)my_insert(x);}}my_search();printf("%d",ans+1);return 0;
}