-
-
-
-
- 传送门
- 思路
- 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=)