本文共 1748 字，大约阅读时间需要 5 分钟。
转化题意可以得到 我们求得就是 所有串的差分串的LCS
SAM水过就好啦
#include #include #include #include #include #define inf 20021225#define ll long long#define mxn 110using namespace std;struct edge{int to,lt;}e[mxn*4]; int in[mxn*4],cnt;struct node{int fa,len;map mp;}t[mxn*4];int poi,rt,lt,ch[mxn],n;int mx[mxn*4],mn[mxn*4];void add(int x,int y){ e[++cnt].to=y;e[cnt].lt=in[x];in[x]=cnt;}void pre(){rt=lt=++poi;memset(mn,48,sizeof(mn));}void insert(int c){ int p=lt, np=lt=++poi; t[np].len=t[p].len+1; for(;p&&!t[p].mp[c];p=t[p].fa) t[p].mp[c]=np; if(!p){t[np].fa=rt; return;} int q=t[p].mp[c]; if(t[q].len==t[p].len+1){t[np].fa=q;return;} int nq=++poi; t[nq].mp=t[q].mp; t[nq].len=t[p].len+1; t[nq].fa=t[q].fa; t[np].fa=t[q].fa=nq; for(;p&&t[p].mp[c]==q;p=t[p].fa) t[p].mp[c]=nq;}void build(){for(int i=2;i<=poi;i++) add(t[i].fa,i);}void init(){memset(mx,0,sizeof(mx));}void find(){ int pos=rt,len=0; for(int i=1;i<=n;i++) { int tmp=ch[i]; if(t[pos].mp[tmp]) pos=t[pos].mp[tmp],len++; else { for(;pos&&!t[pos].mp[tmp];pos=t[pos].fa); if(!pos) pos=rt,len=0; else len=t[pos].len+1,pos=t[pos].mp[tmp]; } //printf("%d\n",len); mx[pos]=max(mx[pos],len); }}void dfs(int x){ for(int i=in[x];i;i=e[i].lt) { dfs(e[i].to); mx[x]=max(mx[x],min(mx[e[i].to],t[x].len)); } mn[x]=min(mn[x],mx[x]);}int a[mxn];int main(){ int T; scanf("%d",&T); for(int i=1;i<=T;i++) { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(i>1) ch[i-1]=a[i]-a[i-1]; } n--; if(i==1) { pre(); for(int i=1;i<=n;i++) insert(ch[i]); build(); } else init(),find(),dfs(rt); } int ans=0; for(int i=1;i<=poi;i++) ans=max(ans,mn[i]); printf("%d\n",ans+1); return 0;}
转载于:https://www.cnblogs.com/hanyuweining/p/10321907.html