bzoj 1398: Vijos1382寻找主人 Necklace （后缀自动机）

题目描述

传送门

题目大意：判断两个串是否同构，并超出与其同构的最小表示。

题解

这道题貌似是最小表示法的裸题，但是我们并不会最小表示法，所以就用后缀自动机来做了，但是这道题的内存按理来说是不能写后缀自动机的，数据比较水就过了。。。。 将第一串扩大两倍，然后建立后缀自动机。用第二个串在上面匹配，如果匹配的长度等于串长那么就同构。至于最小表示，直接从后缀自动机的根开始每次找最小的子节点向后走，走到串长的长度就停止。

代码

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define N 4000003 using namespace std; int ch[N][10],fa[N],l[N],n,cnt,np,p,nq,q,last,root; char s[N]; void extend(int x) { int c=s[x]-'0'; p=last; np=++cnt; last=np; l[np]=l[p]+1; for (;!ch[p][c]&&p;p=fa[p]) ch[p][c]=np; if (!p) fa[np]=root; else{ q=ch[p][c]; if (l[q]==l[p]+1) fa[np]=q; else { nq=++cnt; l[nq]=l[p]+1; memcpy(ch[nq],ch[q],sizeof(ch[nq])); fa[nq]=fa[q]; fa[q]=fa[np]=nq; for (;ch[p][c]==q;p=fa[p]) ch[p][c]=nq; } } } bool solve() { int now=root; int mx=0,tmp=0; for (int i=1;i<=n;i++) { int x=s[i]-'0'; if (ch[now][x]) now=ch[now][x],tmp++; else { while (now&&!ch[now][x]) now=fa[now]; if (!now) now=root,tmp=0; else tmp=l[now]+1,now=ch[now][x]; } mx=max(mx,tmp); } // cout<<mx<<endl; if (mx<n) return false; return true; } int main() { freopen("a.in","r",stdin); scanf("%s",s+1); n=strlen(s+1); last=root=++cnt; for (int i=1;i<=n;i++) extend(i); for (int i=1;i<=n;i++) extend(i); scanf("%s",s+1); if (solve()) printf("Yes\n"); else { printf("No\n"); return 0; } int now=root; for (int i=1;i<=n;i++) { for (int j=0;j<=9;j++) if (ch[now][j]) { now=ch[now][j]; printf("%d",j); break; } } printf("\n"); }