题目描述
母亲节就要到了, 小 H 准备送给她一个特殊的项链. 这个项链可以看作一个用小写字
母组成的字符串, 每个小写字母表示一种颜色. 为了制作这个项链, 小 H 购买了两个机器. 第一个机器可以生成所有形式的回文串, 第二个机器可以把两个回文串连接起来, 而且第二个机器还有一个特殊的性质: 假如一个字符串的后缀和一个字符串的前缀是完全相同的, 那么可以将这个重复部分重叠. 例如: aba 和 aca 连接起来, 可以生成串 abaaca 或 abaca. 现在给出目标项链的样式, 询问你需要使用第二个机器多少次才能生成这个特殊的项链.
输入
输入数据有多行, 每行一个字符串, 表示目标项链的样式.
输出
多行, 每行一个答案表示最少需要使用第二个机器的次数.
样例输入
- abcdcba
- abacada
- abcdef
样例输出
0
2
5
提示
每个测试数据, 输入不超过 5 行
每行的字符串长度小于等于 50000
将每个回文串看作一个线段, 那么问题就变成至少多少个线段能将区间全部覆盖. 用 manacher 求一下以每个位置为中心的最长回文串, 将其视为一个线段然后按左端点排序贪心选线段即可.
- #include<set>
- #include<map>
- #include<queue>
- #include<stack>
- #include<cmath>
- #include<cstdio>
- #include<vector>
- #include<bitset>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- #define ll long long
- using namespace std;
- char s[100010];
- int len[100010];
- int n;
- int mx,num;
- struct miku
- {
- int l,r;
- }a[100010];
- bool cmp(miku a,miku b)
- {
- return a.l<b.l;
- }
- int main()
- {
- while(scanf("%s",s+1)!=EOF)
- {
- n=strlen(s+1);
- for(int i=n;i>=1;i--)
- {
- s[i<<1]=s[i];
- s[i<<1|1]='&';
- }
- n=n<<1|1;
- s[0]='%';
- s[1]='&';
- s[n+1]='^';
- mx=0,num=0;
- for(int i=1;i<=n;i++)
- {
- len[i]=mx>i?min(len[num*2-i],mx-i):1;
- while(s[i+len[i]]==s[i-len[i]])
- {
- len[i]++;
- }
- if(mx<i+len[i])
- {
- mx=i+len[i];
- num=i;
- }
- }
- for(int i=1;i<=n;i++)
- {
- a[i].l=i-len[i]+1;
- a[i].r=i+len[i]-1;
- }
- sort(a+1,a+1+n,cmp);
- int r=0,ans=0,i=1;
- while(i<=n)
- {
- int sum=0;
- while(a[i].l-1<=r&&i<=n)
- {
- sum=max(sum,a[i].r);
- i++;
- }
- ans++;
- r=sum;
- if(r==n)
- {
- break;
- }
- }
- printf("%d\n",ans-1);
- }
- }
来源: http://www.bubuko.com/infodetail-2947318.html