bzoj1396_bzoj3771

全栈程序员-用户IM • 2022年8月12日下午1:36 • 未分类

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1396

题目大意：

bzoj1396_bzoj3771

题解：后缀自动机，只出现一次，那么就是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 }