-
-
-
-
- 傳送門
- 思路
- Manacher 算法
- 特殊字元
- 回文半徑
- 算法與實作
- 本質不同的回文串個數
- 正解
- 參考代碼
- 總結
-
-
-
傳送門
思路
唉，我太弱了，什麼都不會，這道題各路神仙都說是模闆題，但我覺得完全不可做，唉，我太弱啦！神仙們太強啦！
我不打算再學回文樹1了，我打算用神仙流傳的 Manacher + SAM 來做。在此之前，我們先回顧一下 Manacher 算法以及回文串的相關知識。
Manacher 算法
特殊字元
Manacher 算法要在每兩個字元間插入一個從未出現過的特殊字元（包括首位），也就是說長度為 n n 的字元串将會插入 n+1n+1 個特殊字元。約定我們的特殊字元為 #。
插入特殊字元後，所有回文串的長度都變成了奇數，也就是說回文串的對稱軸一定在一個字元上。
回文半徑
回文半徑表示一個回文串最左或者最右的字元與其對稱軸的距離，準确地說是對稱軸到邊界的字元數（包含對稱軸和邊界）。
我們設 RLi R L i 表示以第 i i 個字元為對稱軸的最長回文串的回文半徑。
RLiRLi 還表示以 i i 為對稱軸的最長回文串長度加一。
算法與實作
自己想。百度去。
本質不同的回文串個數
定理：本質不同的回文串個數為 O(n)O(n)。
證明
考慮 Manacher 算法的過程。當我們擴張觸及範圍時，說明我們可能找到一個新的回文子串。如果我們沒有擴張，那麼這個回文子串一定已經被找到過了。
由于擴張次數是 O(n) O ( n ) 的，是以本質不同的回文子串是 O(n) O ( n ) 的。
證畢。
推論：本質不同的回文串的總長度為 O(n2) O ( n 2 ) 。
證明
由定理，顯然。我們也可以考慮構造這樣一個字元串： aaaaa⋯ a a a a a ⋯ ，顯然本質不同的回文串的總長度是 O(n2) O ( n 2 ) 的。
正解
我們來整理一下思路。顯然我們可以通過 Manacher 算法得到本質不同的所有回文串，個數為 O(n) O ( n ) 個。如果我們知道了各回文串的出現次數，問題就解決了。
提到求各回文串的出現次數，自然會想到字尾自動機。那麼我們再來回憶一下字尾自動機。我們可以求出 right r i g h t 集合的大小，然後把每個字元串放到字尾自動機上跑，停在的結點就是出現次數。
但是以上操作的時間複雜度與串總長同階，是以以上算法的時間複雜度是 O(n2) O ( n 2 ) 的。 有沒有加速這個過程的方法呢？
假設某個子串以第 i i 個字元結尾，那它一定是 1∼i1∼i 的字尾，換句話說，它在字尾連結樹中一定是 i i 對應結點的祖先。我們倍增向上跳，直到長度滿足要求即可。這樣，單次查詢的時間複雜度為 O(logn)O(logn)，算法的整體時間複雜度為 O(nlogn) O ( n log n ) 。
參考代碼
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
INT_PUT a = ; bool positive = true;
char ch = getchar();
while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
if (ch == '-') { positive = false; ch = getchar(); }
while (std::isdigit(ch)) { a = a * - (ch - '0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[]; int length = ;
if (x < ) putchar('-'); else x = -x;
do buffer[length++] = -(x % ) + '0'; while (x /= );
do putchar(buffer[--length]); while (length);
}
const int maxn = int() + ;
int n;
char str[maxn];
void readstr()
{
char ch = getchar();
while (!std::isalpha(ch)) ch = getchar();
while (std::isalpha(ch))
{
str[++n] = ch;
ch = getchar();
}
}
struct SuffixAutomaton
{
static const int alphabet = ;
static inline int code(char ch) { return ch - 'a'; }
struct Node
{
int len;
int suffix;
int ch[alphabet];
} nodes[maxn * ];
int size, last;
SuffixAutomaton() { nodes[last = size++].suffix = -; }
int cnt;
int leaf[maxn];
void extend(char ch)
{
int x = code(ch);
int p = last;
int cur = leaf[++cnt] = last = size++;
nodes[cur].len = nodes[p].len + ;
for (; ~p && !nodes[p].ch[x]; p = nodes[p].suffix)
nodes[p].ch[x] = cur;
if (!~p)
{
nodes[cur].suffix = ;
return;
}
int q = nodes[p].ch[x];
if (nodes[p].len + == nodes[q].len)
{
nodes[cur].suffix = q;
return;
}
int clone = size++;
nodes[clone] = nodes[q];
nodes[clone].len = nodes[p].len + ;
nodes[q].suffix = nodes[cur].suffix = clone;
for (; ~p && nodes[p].ch[x] == q; p = nodes[p].suffix)
nodes[p].ch[x] = clone;
}
int k;
int parent[][maxn * ];
int buf[maxn * ];
int sort[maxn * ];
int weight[maxn * ];
void init()
{
while ( << k <= size) k++;
for (int i = ; i <= size; i++)
parent[][i] = nodes[i].suffix;
for (int i = ; i <= k; i++)
for (int j = ; j <= size; j++)
parent[i][j] = parent[i - ][parent[i - ][j]];
for (int i = ; i < size; i++) buf[nodes[i].len]++;
for (int i = ; i < size; i++) buf[i] += buf[i - ];
for (int i = size - ; ~i; i--) sort[--buf[nodes[i].len]] = i;
for (int i = ; i <= n; i++)
weight[leaf[i]] = ;
for (int i = size - ; i; i--)
{
int node = sort[i];
weight[parent[][node]] += weight[node];
}
}
LL query(int pos, int len)
{
int node = leaf[pos];
for (int i = k; ~i; i--)
{
if (nodes[parent[i][node]].len < len) continue;
node = parent[i][node];
}
return (LL)len * weight[node];
}
} sam;
struct Manacher
{
int size;
char str[maxn * ];
int f[maxn * ];
void init()
{
str[] = '#';
for (int i = ; i <= n; i++)
{
str[(i << ) - ] = ::str[i];
str[i << ] = '#';
}
size = * n + ;
}
void manacher(const std::function<void(int, int)> func)
{
int center = ;
int maxr = ;
for (int i = ; i < size; i++)
{
if (i <= maxr)
f[i] = std::min(f[(center << ) - i], maxr - i + );
else
f[i] = ;
while (i - f[i] >= && i + f[i] < size && str[i - f[i]] == str[i + f[i]])
{
f[i]++;
if (i + f[i] - > maxr)
{
maxr = i + f[i] - ;
center = i;
if (str[maxr] != '#')
func(((maxr + ) >> ), f[i]);
}
}
}
}
} manacher;
LL ans;
void callback(int pos, int len)
{
ans = std::max(ans, sam.query(pos, len));
}
void run()
{
readstr();
for (int i = ; i <= n; i++)
sam.extend(str[i]);
sam.init();
manacher.init();
manacher.manacher(callback);
printOut(ans);
}
int main()
{
run();
return ;
}
總結
字尾自動機第一次跳躍要重定向至
cur
。
Manacher 一般是先擴張，再更新
maxr
，這裡需要同時更新
maxr
。當然，第一步是要确定答案下界。
- 什麼是回文樹？回文樹又稱回文自動機（但是字尾樹不是字尾自動機），它在處理回文子串時有超強功效。 ↩
![【BZOJ1179】【APIO2009】Atm（tarjan+spfa）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)