【BZOJ3790】神奇项链 Manacher+贪心

2022-12-24 08:24:39

【BZOJ3790】神奇项链

Description

母亲节就要到了，小 H 准备送给她一个特殊的项链。这个项链可以看作一个用小写字

母组成的字符串，每个小写字母表示一种颜色。为了制作这个项链，小 H 购买了两个机器。第一个机器可以生成所有形式的回文串，第二个机器可以把两个回文串连接起来，而且第二个机器还有一个特殊的性质：假如一个字符串的后缀和一个字符串的前缀是完全相同的，那么可以将这个重复部分重叠。例如：aba和aca连接起来，可以生成串abaaca或 abaca。现在给出目标项链的样式，询问你需要使用第二个机器多少次才能生成这个特殊的项链。

Input

输入数据有多行，每行一个字符串，表示目标项链的样式。

Output

多行，每行一个答案表示最少需要使用第二个机器的次数。

Sample Input

abcdcba
abacada
abcdef

Sample Output

0
2
5

HINT

每个测试数据，输入不超过 5行

每行的字符串长度小于等于 50000

题解：我们沿用最长双回文串那题里的做法，先在Manacher的同时求出rs[i]，代表以i开头的最长回文串的结尾位置（上一题求的是长度，但都差不多）

然后根据贪心的思想，我们一定是将一些极长回文子串连接起来组成原串（极长回文子串，意思是两边不能再同时延长的回文子串），当然中间可能有重叠部分，然后这就变成了一个用最少的线段来覆盖整个区间的问题，依旧是贪心，始终取右端点最右的线段就好了，时间复杂度O(n)

#include <cstdio>

#include <cstring>

#include <iostream>

char s1[500010],str[1000010];

using namespace std;

int n,len,mx,pos,last,maxx,ans;

int rl[1000010],rs[1000010];

void work()

{

	len=strlen(s1),n=0;

	int i,j,a;

	for(i=0;i<len;i++)	str[n++]='*',str[n++]=s1[i];

	str[n++]='*';

	memset(rs,0,sizeof(rs));

	for(mx=-1,i=0;i<n;i++)

	{

		if(mx>i)	rl[i]=min(mx-i+1,rl[2*pos-i]);

		else	rl[i]=1;

		for(;i+rl[i]<n&&rl[i]<=i&&str[i+rl[i]]==str[i-rl[i]];rl[i]++);

		if(mx<i+rl[i]-1)	mx=i+rl[i]-1,pos=i;

		rs[i-rl[i]+1]=i+rl[i]-1;

	}

	ans=0,last=maxx=rs[0]+2;

	for(i=0;i<n;i+=2)

	{

		if(i==last)	last=maxx,ans++;

		maxx=max(maxx,rs[i]+2);

	}

	printf("%d\n",ans);

	return ;

}

int main()

{

	while(scanf("%s",s1)!=EOF)	work();

	return 0;

}

码农公寓