I Love Palindrome String HDU - 6599 回文树+hash-白红宇

I Love Palindrome String HDU - 6599 回文树+hash

阅读量：5030 次

发布时间：2019-06-12

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

题意：

输出每个长度下的回文串(这些回文串的左半边也需要是回文串)

题解：

直接套上回文树，然后每找到一个回文串就将他hash。

因为符合要求的回文串本身是回文串，左半边也是回文串，所以它左半边也右半边相同，

自己画个图很容易发现的

每次hash判断一下就好了

1 #include 
      
         2 #include 
         3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #include 
                 
                   13 #include 
                  
                    14 15 #define pi acos(-1.0) 16 #define eps 1e-9 17 #define fi first 18 #define se second 19 #define rtl rt<<1 20 #define rtr rt<<1|1 21 #define bug printf("******\n") 22 #define mem(a, b) memset(a,b,sizeof(a)) 23 #define name2str(x) #x 24 #define fuck(x) cout<<#x" = "<
                   
                    <
                    
                     = 0; --i) {108 cnt[fail[i]] += cnt[i];109 if (vis[i]) ans[len[i]] += cnt[i];110 }111 //逆序累加，保证每个点都会比它的父亲节点先算完，于是父亲节点能加到所有子孙112 }113 } pam;114 115 int main() {116 // FIN;117 p[0] = 1;118 for (int i = 1; i < maxn; ++i) p[i] = p[i - 1] * seed;119 while (~sfs(s + 1)) {120 int n = strlen(s + 1);121 pam.init();122 for (int i = 1; i <= n; ++i) {123 HA[i] = HA[i - 1] * seed + s[i];124 pam.add(s[i], i);125 ans[i] = 0;126 }127 pam.count();128 for (int i = 1; i <= n; ++i) printf("%d%c", ans[i], (i == n ? '\n' : ' '));129 }130 return 0;131 }