判断回文可以用 hash 判定原串与逆串是否相等，找某个中心扩展的回文串可以用原串和逆串最长公共前缀。
允许字符串重排时，回文与每个字符出现的奇偶性有关。
一个串的本质不同回文子串个数是关于串长线性的，长度为 $n$ 的串在末尾加一个字符 $c$ 后如果想多一个本质不同的回文子串，那么必然是当前串的最长回文后缀。
没有长度为 2 的（或偶数长度）回文子串意味着任意连续 2 个字符不同，没有长度大于 1 的回文子串意味着任意连续 3 个字符不同。
最长回文子序列是原串和逆串的最长公共子序列。
回文只限制了等于和不等于的关系，可以用最小表示法表示回文。规模较大，限制较少时，也可采用下述方法表示 border。
从回文中心入手比较方便解决问题。例如从一个串里选择两个不相交的子区间拼成最长回文串，如果回文中心所在的那个区间没有包含极大回文子串，那么可以调整为包含极大回文子串。
回文 border 是回文串的回文前缀，也是它的回文后缀。由于周期的性质，border 可以按照长度之差分为 $\mathcal{O}(\log |S|)$ 组，每一组称为一个 border series，其中同组 border 的长度之差相等，具体来说是将 border 与更小 border 的长度之差相等的 border 分为一组（虽然倒过来分也没关系）。
在字符串末尾增加一个字符后，回文后缀只会有三种事件：后缀变长、后缀消失、后缀出现。其中后缀消失和后缀出现的总次数关于长度线性，而同一个 border series 的后缀除最长的 border 外其他 border 要么同时变长、要么同时消失。
回文树可以维护字符串的本质不同回文子串，并支持在两端添加字符。
AC 自动机计算 fail 的复杂度基于所有节点的深度之和不超过总串长，在后缀树和回文树上则没有这样的性质。如果对 kmp、AC 自动机、后缀树、回文树需要支持末尾增删操作，有两种做法可以选择，一种是记录 border series 强行计算，一种是额外记录每个节点增加某个字符能到达的节点信息，前者是 $\mathcal{O}(\log |S|)$ 的，后者是 $\mathcal{O}(\sum)$ 或 $\mathcal{O}(\log \sum)$ 的。
考虑任意一组 border（不只是回文 border），不妨设 border 长度从小到大依次为 $l_1, l_2, \cdots, l_{m - 1}$ ，并且我们约定 $l_0 = 0, l_m = |S|$，那么对于任意的 $i = 1, 2, \cdots, m - 1$，要么有 $l_{i + 1} > 2 l_i$，要么存在 $j = 0, 1, \cdots, i - 1$ 使得 $l_{i + 1} = 2 l_i - l_j$，而且当 $l_{i + 1} - l_i$ 是 $l_i - l_{i - 1}$ 的倍数时，必有 $l_{i + 1} = 2 l_i - l_{i - 1}$。此外，这些性质限制的序列一定能表示成某个字符串 $S$ 的 border。

tangjz的博客

博客

Palindrome 扫题（完成度：100%）

ACdream

Aizu

AtCoder

CodeChef

CodeForces

CSU

FZU

HackerRank

HDU

HihoCoder

HIT

HUST

Kattis

LightOJ

NBUT

OpenJudge

POJ

SCU

SGU

SPOJ

TopCoder

UESTC

URAL

UVA

UVALive

Z-Training

ZOJ

总结

评论

发表评论