【Vijos1677】陶陶的名字

Source and Judge

Vijos1677

Problem

【Description】
某一天,陶陶想把自己的名字涂在墙上。由于他的名字太长,为了省事,他从自己名字的开头截取了一段作为模板。我们不妨设这个模板的长度为l,陶陶的名字的长度为L,那么有1≤l≤L。
然后陶陶会用这个模板进行若干次喷涂,喷出自己的名字(后一次喷涂会覆盖前一次喷涂的结果,例如当前墙上已经有abc三个字符,那么如果在c处进行喷涂,就会得到ababc)。
陶陶喷涂名字总是从前向后喷的,假设陶陶喷涂了k次,这k次喷涂按时间顺序第i次喷涂的位置是s[i],那么s[i]<s[i+1]。
【Input】
陶陶的名字
【Output】
最短的模版长度
【Limited conditions】
对于10%的数据, n≤200
对于30%的数据, n≤1000
对于100%的数据,n≤1000000
【Sample input】
abcabababc
【Sample output】
3
【Sample explanation】
陶陶的名字是abcabababc,最短的模版是abc。
注意,印刷只能从前向后印

Record

1h

Analysis

请先思考

akc的突破口:最后面一定是一样的
一起yy出来但最后没用的:满足二分性
正解:先跑一次kmp,得到nxt数组
对于一个i,尝试验证其$p[i]$是否可行
回顾一下:$S(1,p[i])=S(i-p[i]+1,i)$
定义lst=最后一个$p[i]=0$,那么在kmp中,这意味着一切开始,此后的最长公共前缀后缀都不会越过这里

①$p[i]>=p[i-p[i]+1]$
显然是可行的,直接叠过去就好
②$p[i]<p[i-p[i]+1]-1$
如果$lst<=p[i]$,那么这段空缺中的每一个元素都不为0,即都能填充
反之,如果$lst>p[i]$,那么一定所有公共前缀后缀无法越过这里,则存在一部分空缺无法填充
画画图就很好懂了

那么接下来就是从最后不停跳,知道情况2的第二种情况出现,则结束。

Code

请先思考
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
void chmax(int &x,int y) {if(x<y) x=y;}
void chmin(int &x,int y) {if(x>y) x=y;}
//*******************全局常量*******************
const int MAXN=1100000;
//*******************全局定义*******************
char s[MAXN];
int nxt[MAXN];
//*******************实现*******************
//*******************主函数*******************
int main()
{
scanf("%s",s+1);
int ln=strlen(s+1);
nxt[1]=0;
int lst=0;
for(int i=2;i<=ln;i++)
{
int j=nxt[i-1];
while(j>0 and s[j+1]!=s[i]) j=nxt[j];
nxt[i]=j+(s[j+1]==s[i]);
if(nxt[i]==0) lst=i;
}
int x=ln;
while(1)
{
if(nxt[x]<x-nxt[x]+1 and nxt[x]<lst) break;
x=nxt[x];
}
printf("%d",x);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-04/陶陶的名字.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%