BZOJ3790神奇项链——manacher+贪心-白红宇

BZOJ3790神奇项链——manacher+贪心

阅读量：4657 次

发布时间：2019-06-09

本文共 1132 字，大约阅读时间需要 3 分钟。

题目描述

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

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

输入

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

输出

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

样例输入

abcdcba

abacada

abcdef

样例输出

提示

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

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

将每个回文串看作一个线段，那么问题就变成至少多少个线段能将区间全部覆盖。用manacher求一下以每个位置为中心的最长回文串，将其视为一个线段然后按左端点排序贪心选线段即可。

#include
       
        #include
        #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #define ll long longusing 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
                  
                   =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

转载于:https://www.cnblogs.com/Khada-Jhin/p/10355961.html

你可能感兴趣的文章