3790: 神奇项链
Time Limit: 10 Sec
Memory Limit: 64 MB
[
Submit][
Status][
Discuss]
Description
母亲节就要到了，小 H 准备送给她一个特殊的项链。这个项链可以看作一个用小写字
母组成的字符串，每个小写字母表示一种颜色。为了制作这个项链，小 H 购买了两个机器。第一个机器可以生成所有形式的回文串，第二个机器可以把两个回文串连接起来，而且第二个机器还有一个特殊的性质：假如一个字符串的后缀和一个字符串的前缀是完全相同的，那么可以将这个重复部分重叠。例如：aba和aca连接起来，可以生成串abaaca或 abaca。现在给出目标项链的样式，询问你需要使用第二个机器多少次才能生成这个特殊的项链。
Input
输入数据有多行，每行一个字符串，表示目标项链的样式。
Output
多行，每行一个答案表示最少需要使用第二个机器的次数。
Sample Input
abcdcba abacada abcdef
Sample Output
0 2 5
HINT
每个测试数据，输入不超过 5行
每行的字符串长度小于等于 50000
Source
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 500005;
char a[N],s[N];
int la,id,mx,n,ans,p[N];
struct data{ int l, r; }sa[N];
void init(){
memset(s,0,sizeof(s)); memset(p,0,sizeof(p));
id = mx = la = n = ans = 0;
}
bool cmp( data a, data b ){ return a.l < b.l || (a.l==b.l&&a.r>b.r); }
void manacher(){
for( int i = 1; i <= n; i++ ){
if( i < mx ){ p[i] = min(mx-i,p[id*2-i]);}
else p[i] = 1;
while( s[i+p[i]] == s[i-p[i]] ) p[i]++;
if( i+p[i] > mx ){
mx = i+p[i]; id = i;
}
}
}
int main(){
while(~scanf("%s", a)){
init(); la = strlen(a);
s[0] = '*';
for( int i = 0; i < la; i++ ) s[++n] = '#', s[++n] = a[i]; s[++n] = '#';
manacher();
for( int i = 1; i <= n; i++ ) sa[i].l = i-p[i]+1, sa[i].r = i+p[i]-1;
std::sort(sa+1,sa+n+1,cmp);
int r = sa[1].r, tail = 2;
while( r < n ){
int lim = r;
while( tail <= n && sa[tail].l <= r ) lim = max(lim,sa[tail].r), tail++;
ans++; r = lim;
}
printf("%d\n", ans);
}
return 0;
}
