BZOJ1535: [POI2005]Sza-Template

1535: [POI2005]Sza-Template

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 240 Solved: 121
[Submit][Status]

Description

Byteasar 想在墙上涂一段很长的字符,他为了做这件事从字符的前面一段中截取了一段作为模版. 然后将模版重复喷涂到相应的位置后就得到了他想要的字符序列.一个字符可以被喷涂很多次,但是一个位置不能喷涂不同的字符.做一个模版很费工夫,所以他想要模版的长度尽量小,求最小长度是多少.拿样例来说 ababbababbabababbabababbababbaba , 模版为前8个字符ababbaba, 喷涂的过程为: ababbababbabababbabababbababbaba

Input

输入一行最多不超过500 000 个最少1个小写字符.

Output

一个长度表示模版最小的长度.

Sample Input

ollowing input data:
ababbababbabababbabababbababbaba

Sample Output

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 1000000000
13 #define maxn 550000
14 #define maxm 500+100
15 #define eps 1e-10
16 #define ll long long
17 #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 1000000007
23 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
",ans);
74     return 0;
75 }

View Code