哇哦~ 想不到我有生之年竟然能够做出字符串的题目ヾ (??▽?) ノ虽然这题比较裸但依然灰常开心!
首先有一个棒棒的性质: 本质不同的回文串最多有 O(n) 个. 首先 manacher 把它们都找出来, 然后问题就变成了给定 n 个子串, 求它们在原串中出现的次数. 求出 height 然后二分一下即可(这个好像是 SA 的基础操作?).
- #include <bits/stdc++.h>
- using namespace std;
- #define maxn 601550
- #define CNST 22
- int n, N, m, p1[maxn], p2[maxn], rk[maxn], bits[CNST];
- int p[maxn], rec[maxn], t[maxn], y[maxn], Log[maxn];
- int num[maxn], SA[maxn], ST[maxn][CNST];
- long long ans;
- char a[maxn], s[maxn];
- void pre()
- {
- s[0] = s[1] = '#'; s[2 * n + 2] = '?';
- for(int i = 0; i <n; i ++) s[i * 2 + 2] = a[i], s[i * 2 + 3] = '#';
- N = n * 2 + 2;
- }
- void Up(int &x, int y) { x = (x> y) ? x : y; }
- void manacher()
- {
- int mid = 0, mr = 0;
- for(int i = 0; i <N; i ++)
- {
- if(i <= mr) p[i] = min(p[(mid << 1) - i], p[mid] + mid - i);
- else p[i] = 1; Up(rec[i + p[i] - 1], p[i]);
- while(s[i + p[i]] == s[i - p[i]])
- {
- p[i] ++;
- Up(rec[i + p[i] - 1], p[i]);
- }
- if(p[i] + i - 1> mr) mr = p[i] + i - 1, mid = i;
- }
- }
- //SA
- void Rsort(int *p, int *x, int *id)
- {
- for(int i = 1; i <= m; i ++) t[i] = 0;
- for(int i = 1; i <= n; i ++) t[p[i]] ++;
- for(int i = 1; i <= m; i ++) t[i] += t[i - 1];
- for(int i = n; i>= 1; i --) x[t[p[id[i]]] --] = id[i];
- }
- bool cmp(int x, int y) { return y && (p1[x] == p1[y] && p2[x] == p2[y]); }
- void Get_SA()
- {
- m = 128;
- for(int k = 0; bits[k] <= n; k ++)
- {
- for(int i = 1; i <= n; i ++)
- p1[i] = rk[i], p2[i] = (i + bits[k] <= n) ? rk[i + bits[k]] : 0;
- Rsort(p2, y, num); Rsort(p1, SA, y);
- for(int i = 1, p = 0; i <= n; m = p, i ++)
- rk[SA[i]] = cmp(SA[i - 1], SA[i]) ? p : ++ p;
- if(m>= n) break;
- }
- }
- void Get_Height()
- {
- for(int i = 1, k = 0; i <= n; i ++)
- {
- if(k) k --;
- int j = SA[rk[i] - 1];
- while(max(i, j) + k - 1 <= n && a[j + k - 1] == a[i + k - 1]) k ++;
- ST[rk[i]][0] = k;
- }
- }
- void Build()
- {
- for(int j = 1; j <CNST; j ++)
- for(int i = 1; i + bits[j] - 1 <= n; i ++)
- ST[i][j] = min(ST[i][j - 1], ST[i + bits[j - 1]][j - 1]);
- }
- int RMQ(int x, int y)
- {
- if(y < x) swap(x, y);
- int k = Log[y - x + 1];
- return min(ST[x][k], ST[y - bits[k] + 1][k]);
- }
- int Query(int x, int len)
- {
- int l = 1, r = rk[x], ans2 = rk[x], ans1 = rk[x] + 1;
- while(l <= r)
- {
- int mid = (l + r)>> 1;
- if(RMQ(rk[x], mid)>= len) ans1 = mid, r = mid - 1;
- else l = mid + 1;
- }
- ans1 --; l = rk[x] + 1, r = n;
- while(l <= r)
- {
- int mid = (l + r)>> 1;
- if(RMQ(rk[x] + 1, mid)>= len) ans2 = mid, l = mid + 1;
- else r = mid - 1;
- }
- return ans2 - ans1 + 1;
- }
- void init()
- {
- Log[0] = -1; for(int i = 1; i <maxn; i ++) Log[i] = Log[i>> 1] + 1;
- bits[0] = 1; for(int i = 1; i <CNST; i ++) bits[i] = bits[i - 1] << 1;
- for(int i = 1; i < maxn; i ++) num[i] = i;
- }
- int main()
- {
- init();
- scanf("%s", a); n = strlen(a);
- pre(); manacher();
- for(int i = 1; i <= n; i ++) rk[i] = a[i - 1];
- Get_SA(); Get_Height(); Build();
- for(int i = 1; i < N; i ++)
- {
- if(s[i] == '#') continue;
- int r = (i - 2)>> 1;
- int l = r - rec[i] + 1; r ++, l ++;
- int t = Query(l, r - l + 1);
- ans = max(ans, 1ll * t * (r - l + 1));
- }
- printf("%lld\n", ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2854415.html