题目大意：用最少的回文串覆盖整个字符串，可重叠。

题解：Manacher+贪心

md最近好几个线段覆盖的题都没看出来。

Manacher算出以每个字符为中心的回文串，就是一个线段，计算出左端点i-Len[i]+1和

右端点i+Len[i]-1，然后贪心用每个线段覆盖区间就好了，两个回文串，就是两个区间是

可以重叠的。贪心嘛，就是以左端点为第一关键字，右端点为第二关键字排序。没次找

能与上一条线段相接的右端点最大的就行了。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #define maxn 50009using namespace std; char s[maxn*2],str[maxn*2];int len,Len[maxn*2];struct X{    int l,r;}xd[maxn*2]; bool cmp(X a,X b){    if(a.l!=b.l)return a.l
         
          b.r;} void getstr(){    int k=0;str[k++]='$';    for(int i=0;i
          
           i)Len[i]=min(Len[2*id-i],mx-i); else Len[i]=1; while(str[i+Len[i]]==str[i-Len[i]])Len[i]++; if(i+Len[i]>mx)mx=i+Len[i],id=i; }} int main(){ while(scanf("%s",&s)!=EOF){ len=strlen(s); Manacher(); for(int i=1;i