设为首页 加入收藏

TOP

HDU 5340-Three Palindromes(Manacher算法)
2015-11-21 00:56:15 来源: 作者: 【大 中 小】 浏览:1次
Tags：HDU 5340-Three Palindromes Manacher 算法

?
题意：问是否能将字符串str分解为三段非空的回文串。
思路：我们根据Manacher算法对字符串进行处理，处理过程中产生的P数组，我们可以得到两个数组first和last。
first存储的是第一个回文串的半径可能值。
last存储的是第三个回文串的半径可能值。
根据first和last我们可以枚举第一个回文串和第三个回文串，然后根据半径找出第二个回文串的初始位置和结束位置。然后计算出第二个回文串的中点：
1.如果ll>rr，则第二个字符串的长度为负数，pass
2.如果p[mid]=1，说明第二个回文串为”#”，相当于空，pass
3.如果三个子字符串的长度加起来大于len，证明符合长度，跳出来即可。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include
              #pragma comment(linker, /STACK:102400000,102400000) using namespace std; typedef long long LL; const int inf=0x3f3f3f3f; const double pi= acos(-1.0); const double esp=1e-6; const int maxn=110010; char str[maxn]; char s[maxn*2]; int p[maxn*2]; int len; int first[maxn*2]; int last[maxn*2]; void Manacher() { int i; s[0]='$'; s[1]='#'; for(i=0;i
              
               i) p[i]=min(p[2*id-i],p[id]+id-i); else p[i]=1; while(s[i+p[i]]==s[i-p[i]]) p[i]++; if(p[i]+i>p[id]+id) { id=i; } if(p[i]>MaxL) MaxL=p[i]; } } int main() { int T; scanf(%d,&T); while(T--){ scanf(%s,&str); len=strlen(str); Manacher(); int l1=0,r1=0; for(int i=2;i<=len-2;i++){ if(i==p[i]) first[l1++]=i; if(p[i]==len-i) last[r1++]=i; } int flag=0; int ll,rr,mid; for(int i=0;i
               
                rr) continue; mid=(ll+rr)/2; if(ll==rr&&s[mid]=='#') continue; if(p[first[i]]*2-1+p[mid]*2-1+p[last[j]]*2-1>=len+1){ flag=1; break; } } if(flag) break; } if(flag) puts(Yes); else puts(No); } return 0; }

?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：zoj 1395 Door Man 欧拉回路 下一篇：C++中类定义的细节

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: