首页 > 代码库 > bzoj3790 神奇项链
bzoj3790 神奇项链
Description
母亲节就要到了，小 H 准备送给她一个特殊的项链。这个项链可以看作一个用小写字
母组成的字符串，每个小写字母表示一种颜色。为了制作这个项链，小 H 购买了两个机器。第一个机器可以生成所有形式的回文串，第二个机器可以把两个回文串连接起来，而且第二个机器还有一个特殊的性质：假如一个字符串的后缀和一个字符串的前缀是完全相同的，那么可以将这个重复部分重叠。例如：aba和aca连接起来，可以生成串abaaca或 abaca。现在给出目标项链的样式，询问你需要使用第二个机器多少次才能生成这个特殊的项链。
Input
输入数据有多行，每行一个字符串，表示目标项链的样式。
Output
多行，每行一个答案表示最少需要使用第二个机器的次数。
Sample Input
abcdcba
abacada
abcdef
abacada
abcdef
Sample Output
0
2
5
2
5
HINT
每个测试数据，输入不超过 5行
每行的字符串长度小于等于 50000
manacher+贪心
这是我写的manacher第一题啊
这是一个O(n)的找回文串的算法
首先找出以每一位为中心的最长回文子串的区间，问题变成取最少的区间完全覆盖整个区间
排个序贪心就好了。显然是相同个数的区间尽量凑出右边界尽可能大的更优
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971using namespace std;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}inline void write(LL a){ if (a<0){printf("-");a=-a;} if (a>=10)write(a/10); putchar(a%10+‘0‘);}inline void writeln(LL a){write(a);printf("\n");}int len,cnt,tot,now,ans;char ch[100010],s[100010];int p[100010];struct srt{int l,r;}a[100010];bool operator <(srt a,srt b){return a.l<b.l||a.l==b.l&&a.r<b.r;}inline void manacher(){ cnt=tot=0;int mx=0,id=0; for (int i=1;i<=len;i++) { s[++cnt]=‘#‘; s[++cnt]=ch[i]; } s[++cnt]=‘#‘; s[0]=‘$‘; for (int i=2;i<cnt;i++) { if (p[id]+id>i)p[i]=min(p[2*id-i],p[id]-(i-id)); else p[i]=1; while (s[i+p[i]]==s[i-p[i]])p[i]++; if (p[i]+i>p[id]+id)id=i; } memset(a,0,sizeof(a)); for (int i=1;i<=cnt;i++) { int res=p[i]-1; int l=i-res,r=i+res; if (l%2)l++;if (r%2)r--; l/=2;r/=2; if (l>r)continue; a[++tot].l=l; a[tot].r=r; }}inline void work(){ len=strlen(ch+1); manacher(); sort(a+1,a+tot+1); now=ans=0;int i=1; while (now!=len) { int to=-1; while (a[i].l<=now+1&&i<=tot) to=max(to,a[i].r),i++; now=to;ans++; } printf("%d\n",ans-1);}int main(){ while (~scanf("%s",ch+1))work();}
bzoj3790 神奇项链
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。