首页 > 代码库 > BZOJ1535: [POI2005]Sza-Template
BZOJ1535: [POI2005]Sza-Template
1535: [POI2005]Sza-Template
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 240 Solved: 121
[Submit][Status]
Description
Byteasar 想在墙上涂一段很长的字符,他为了做这件事从字符的前面一段中截取了一段作为模版. 然后将模版重复喷涂到相应的位置后就得到了他想要的字符序列.一个字符可以被喷涂很多次,但是一个位置不能喷涂不同的字符.做一个模版很费工夫,所以他想要模版的长度尽量小,求最小长度是多少.拿样例来说 ababbababbabababbabababbababbaba , 模版为前8个字符ababbaba, 喷涂的过程为: ababbababbabababbabababbababbaba
Input
输入一行最多不超过500 000 个最少1个小写字符.
Output
一个长度表示模版最小的长度.
Sample Input
ollowing input data:
ababbababbabababbabababbababbaba
ababbababbabababbabababbababbaba
Sample Output
8
HINT
Source
题解：
想了好长时间发现没想法，看了zrts的题解说是二分，既不懂为何满足单调性，又不懂如何判断一个前缀能否覆盖整个串（现在好像明白怎么覆盖了？扩展kmp？哪天去学学）
然后膜拜jcvb的题解：
覆盖用的串不能超出原串边界，且又要完全覆盖。所以合法串必然是原串前缀且是原串后缀。
KMP后可以得到一棵fail-tree，那么n到根路径上的一个结点对应一个可能合法的串。考虑其中某个串，其长度为len，它在原串的所有出现位置（结束位置）即为以这个结点的为根的子树。如果这个串能够不遗漏地覆盖原串，则它的所有出现位置中相邻两个的距离不超过len。
于是我们要对n到根路径上的每个结点，统计其子树内元素中相邻的差的最大值。考虑沿根下降，则子树元素从{1,2,..,n}开始不断减少。用一个双向链表维护当前属于子树的值，删除的同时更新相邻元素差的最大值。
总复杂度O(n)，常数稍大。
看到网上的题解里有用二分的，表示理解不能。
真是巧妙的思路，双向链表保证了O(1)删除，维护相邻最大差值，从根下降保证了最大差值在增加。orz
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 55000014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26 int x=0,f=1;char ch=getchar();27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29 return x*f;30 }31 int n,mx,ans,tot,nxt[maxn],pre[maxn],head[maxn],next[maxn];32 char s[maxn];33 struct edge{int go,next;}e[maxn];34 bool can[maxn];35 inline void insert(int x,int y)36 {37 e[++tot].go=y;e[tot].next=head[x];head[x]=tot;38 }39 void del(int x)40 {41 nxt[pre[x]]=nxt[x];42 pre[nxt[x]]=pre[x];43 mx=max(mx,nxt[x]-pre[x]);44 for(int i=head[x];i;i=e[i].next)del(e[i].go);45 }46 void dfs(int x)47 {48 if(mx<=x){ans=x;return;}49 int z=0;50 for(int i=head[x],y;i;i=e[i].next)51 if(!can[y=e[i].go])del(y);else z=y;52 if(z)dfs(z);53 }54 int main()55 {56 freopen("input.txt","r",stdin);57 freopen("output.txt","w",stdout);58 scanf("%s",s+1);n=strlen(s+1);59 insert(0,1);60 for(int i=2,j=0;i<=n;i++)61 {62 while(j&&s[j+1]!=s[i])j=next[j];63 if(s[j+1]==s[i])j++;64 next[i]=j;65 insert(j,i);66 }67 for(int i=n;i;i=next[i])can[i]=1;68 for1(i,n)pre[i]=i-1,nxt[i]=i+1;69 pre[1]=nxt[n]=0;70 mx=1;71 ans=n;72 dfs(0);73 printf("%d\n",ans);74 return 0;75 }
BZOJ1535: [POI2005]Sza-Template
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。