HDU 5340 Three Palindromes （Manacher）-白红宇

HDU 5340 Three Palindromes （Manacher）

阅读量：5018 次

发布时间：2019-06-12

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

题意：

　　判断是否能将字符串S分成三段非空回文串。

思路：

　　先预处理出前缀回文串和后缀回文串的位置，将位置分别装入两个集合中，O(n)。

　　针对每个前缀回文串的终点位置，挑出不相交的后缀回文串，对中间那段进行暴力匹配即可。只有20个case，不会超时的。

　　具体的算法参考

1 //#include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
           5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
                10 #include 
               
                 11 #define INF 0x7f7f7f7f 12 #define pii pair
                
                  13 #define LL unsigned long long 14 using namespace std; 15 const int N=20100; 16 int len; //原串长 17 char str[N*2]; //接收原来的串 18 char s[N*2]; 19 int P[N*2]; //保存关于长度的信息（回文长度的一半再加1） 20 vector
                 
                   vect[2]; 21 int cal(int q) 22 { 23 int id=1, mx=1, max1=1; 24 P[0]=1; 25 P[1]=1; 26 for(int i=2; s[i]!='\0'; i++) //考虑以i为中心的回文串 27 { 28 P[i] =i>mx? 1: min( P[2*id-i],mx-i); 29 while(s[i+P[i]]==s[i-P[i]]) //在这比对 30 { 31 if(i-P[i]==1) vect[q].push_back(i+P[i]); //已经匹配 32 P[i]++; 33 } 34 35 36 if(i+P[i]>mx) //更新id和mx的位置 37 { 38 id=i; 39 mx=i+P[i]; 40 } 41 if(P[i]-1>max1) //更新最大值 42 max1=P[i]-1; 43 } 44 return max1; 45 } 46 47 48 49 bool ok() 50 { 51 len=strlen(str); 52 sort(vect[0].begin(), vect[0].end()); 53 sort(vect[1].begin(), vect[1].end()); 54 55 for(int i=0; i
                  
                   r) break; 62 63 while( l
                   
                    >t; 78 while(t--) 79 { 80 scanf("%s",str); 81 len=strlen(str); 82 vect[0].clear(); 83 vect[1].clear(); 84 if(len==3)///特别处理 85 { 86 puts("YES"); 87 continue; 88 } 89 90 s[0]='$'; 91 s[1]='#'; 92 int i=0, j=2; 93 for(; i