大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1396
题目大意：
题解：后缀自动机，只出现一次，那么就是right值为1，那么对于一段1—-L—-R来说，（L—-R)为一个最短识别子串对于（1—-L-1）则可以用R-i+1来更新，对于（L—R）则可以用R-L+1来更新，那么两个线段树来维护即可。
代码：
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<cmath> 6 #define maxn 100005 7 using namespace std; 8 char s[maxn]; 9 int n,m,tot,root; 10 bool v[maxn*2]; 11 struct data{ 12 int last,son[maxn*2][26],val[maxn*2],fa[maxn*2]; 13 void prepare(){root=last=tot=1;} 14 int newnode(int x){val[++tot]=x; return tot;} 15 void extend(int x) 16 { 17 int p=last,np=newnode(val[p]+1); last=np; 18 for (; p && !son[p][x]; p=fa[p]) son[p][x]=np; 19 if (!p) fa[np]=root; 20 else 21 { 22 int q=son[p][x]; 23 if (val[q]==val[p]+1) fa[np]=q; 24 else 25 { 26 int nq=newnode(val[p]+1); 27 memcpy(son[nq],son[q],sizeof(son[nq])); 28 fa[nq]=fa[q];fa[q]=fa[np]=nq; 29 for (; p && son[p][x]==q; p=fa[p]) son[p][x]=nq; 30 } 31 } 32 } 33 void build () 34 { 35 for (int i=1; i<=n; i++) extend(s[i]-'a'); 36 } 37 void whoisfather() 38 { 39 for (int i=1; i<=tot; i++) v[fa[i]]=1; 40 } 41 }SAM; 42 struct T{ 43 int mn[maxn*4]; 44 T(){memset(mn,0x3f,sizeof(mn));} 45 void insert(int z,int l,int r,int x,int y,int w){ 46 if(l>y||r<x) return; 47 if(l>=x&&r<=y){mn[z]=min(mn[z],w);return;} 48 int mid=(l+r)>>1; 49 insert(z*2,l,mid,x,y,w); insert(z*2+1,mid+1,r,x,y,w); 50 } 51 int query(int z,int l,int r,int x){ 52 if(l==r&&l==x) return mn[z]; 53 int mid=(l+r)>>1; 54 if(x<=mid) return min(mn[z],query(z*2,l,mid,x)); 55 else return min(mn[z],query(z*2+1,mid+1,r,x)); 56 } 57 }f,t; 58 int main() 59 { 60 scanf("%s",s+1); n=strlen(s+1); 61 SAM.prepare(); 62 SAM.build(); 63 SAM.whoisfather(); 64 for (int i=1; i<=tot; i++) 65 { 66 if (!v[i]) 67 { 68 int l=SAM.val[i]-SAM.val[SAM.fa[i]],r=SAM.val[i]; 69 f.insert(1,1,n,l,r,r-l+1); 70 if (l>1) t.insert(1,1,n,1,l-1,r); 71 } 72 } 73 for (int i=1; i<=n; i++) printf("%d\n",min(f.query(1,1,n,i),t.query(1,1,n,i)-i+1)); 74 }
View Code
注：oyzx神犇清早刷神题，我就只能默默写渣渣题。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/169941.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...