[APIO2014]回文串 manacher 后缀数组

  1 // luogu-judger-enable-o2
  2 // luogu-judger-enable-o2
  3 #include<bits/stdc++.h>
  4 using namespace std;
  5 #define R register int
  6 #define AC 601000
  7 #define ac 601000
  8 #define LL long long
  9 
 10 int n, m = 127, pos, maxn;
 11 LL ans;
 12 int r[ac], sa[AC], rk[AC], p1[AC], p2[AC], b[AC], d[AC];//第几是谁，你是第几, 两个关键字,临时数组，桶
 13 int st[AC][19], h[AC], last[AC], length[AC];
 14 char ss[AC], s[ac];//原串，扩充串
 15 
 16 inline void upmax(LL &a, LL b){
 17     if(b > a) a = b;
 18 }
 19 
 20 void pre()
 21 {
 22     scanf("%s", ss + 1), n = strlen(ss + 1);
 23     s[0] = ‘$‘, s[1] = ‘#‘;
 24     for(R i = 1; i <= n; i ++) s[i << 1] = ss[i], s[(i << 1) + 1] = ‘#‘;//manacher数组
 25     for(R i = 1; i <= n; i ++) sa[i] = i, rk[i] = ss[i];//初始化后缀数组
 26 }
 27 
 28 void ssort()
 29 {
 30     for(R i = 1; i <= n; i ++) ++ d[p2[i]];
 31     for(R i = 1; i <= m; i ++) d[i] += d[i - 1];
 32     for(R i = 1; i <= n; i ++) b[d[p2[i]] --] = i;//给i分配排名(临时sa数组)
 33     for(R i = 0; i <= m; i ++) d[i] = 0;
 34     
 35     for(R i = 1; i <= n; i ++) ++ d[p1[i]];
 36     for(R i = 1; i <= m; i ++) d[i] += d[i - 1];
 37     for(R i = n; i; i --) sa[d[p1[b[i]]] --] = b[i];//依次给b[i]分配排名
 38     for(R i = 0; i <= m; i ++) d[i] = 0;
 39 }
 40 
 41 void sa_sort()
 42 {
 43     for(R k = 1; k <= n; k <<= 1)
 44     {
 45         for(R i = 1; i <= n; i ++) 
 46             p1[i] = rk[i], p2[i] = rk[i + k];
 47         ssort();
 48         int tmp = 1;
 49         rk[sa[1]] = 1;
 50         for(R i = 2; i <= n; i ++)
 51             rk[sa[i]] = (p1[sa[i]] == p1[sa[i - 1]] && p2[sa[i]] == p2[sa[i - 1]]) ? tmp : ++ tmp;
 52         if(tmp >= n) break;
 53         m = tmp;
 54     }
 55 }
 56 
 57 void manacher()//获取回文串
 58 {
 59     int b = 2 * n;
 60     for(R i = 1; i <= b; i ++)
 61     {
 62         r[i] = (maxn > i) ? min(r[(pos << 1) - i], maxn - i + 1) : 1;
 63         while(s[i - r[i]] == s[i + r[i]]) ++ r[i];
 64         int t = i + r[i] - 1;
 65         if(t > maxn)
 66         {
 67             for(R j = maxn + 1; j <= t; ++ j) 
 68             {
 69                 last[j] = (i << 1) - j;//串的开始是要算的，，，，
 70                 if(s[j] == ‘#‘) continue;
 71                 length[j] = ((j - last[j]) >> 1) + 1;
 72             }
 73             pos = i, maxn = t;
 74         }
 75     }
 76     
 77     /*for(R i = 1; i <= b; i ++)
 78     {
 79         if(s[i] == ‘#‘) continue;
 80         length[i] = ((i - last[i]) >> 1) + 1;//(r - l) / 2 + 1算出字母的长度(个数)
 81     }*/
 82 }
 83 
 84 void build()//求height数组
 85 {
 86     //h[sa[1]] = 0;
 87     for(R i = 1, k = 0; i <= n; i ++)//按照原串顺序求h
 88     {
 89         if(k) -- k;//将k变为上一次的h[i] - 1
 90         int j = sa[rk[i] - 1];
 91         while(ss[i + k] == ss[j + k] && k <= n) ++ k;
 92         h[rk[i]] = k;
 93     }
 94 }
 95 
 96 int t1[AC], t2[AC];//最接近i的2的n次幂的指数，对应的大小
 97 
 98 void get_st()
 99 {
100     int tt = 0, tmp = 1;
101     for(R i = 1; i <= n; i ++) 
102     {
103         st[i][0] = h[i];
104         if(i == (tmp << 1)) tmp <<= 1, ++ tt;
105         t1[i] = tt, t2[i] = tmp;
106     }
107     tmp = 1;
108     for(R i = 1; i <= 18; i ++)
109     {
110         for(R j = 1; j <= n; j ++)
111             st[j][i] = min(st[j][i - 1], st[j + tmp][i - 1]);
112         tmp <<= 1;
113     }    
114 }
115 
116 bool check(int l, int r, int lim)//看min[l, r]是否>= lim
117 {
118     int rnt = 0, len = (r - l + 1);
119     rnt = min(st[l][t1[len]], st[r - t2[len] + 1][t1[len]]);
120     return rnt >= lim;
121 }
122 
123 LL half(int x, int len)//获取出现次数
124 {
125     int l = 1, r = x;
126     while(l < r)//查找前一段里面第一个符合的
127     {
128         int mid = (l + r) >> 1;
129         if(check(mid + 1, x, len)) r = mid;
130         else l = mid + 1;
131     }
132     int ll = l;//记录左边界
133     l = x, r = n;
134     while(l < r)//查找后一段里面最后一个符合的
135     {
136         int mid = (l + r + 1) >> 1;
137         if(check(x + 1, mid, len)) l = mid;
138         else r = mid - 1;
139     }
140     return r - ll + 1;
141 }
142 
143 void work()
144 {
145     int b = 2 * n;
146     for(R i = 1; i <= b; i ++)
147     {
148         if(s[i] == ‘#‘) continue;
149         upmax(ans, 1LL * length[i] * half(rk[last[i] >> 1], length[i]));
150     }
151     printf("%lld\n", ans);
152 }
153 
154 int main()
155 {
156 //    freopen("in.in", "r", stdin);
157     pre();
158     sa_sort();
159     build();
160     get_st();
161     manacher();
162     work();
163 //    fclose(stdin);
164     return 0;
165 }