Palindrome Series 学习笔记


前置知识

border

对于字符串 \(s\) 和整数 \(r(1\le r\le |S|)\) ,存在 \(pre(s,r)=suf(s,r)\) ,则 \(pre(s,r)\) 成为字符串 \(s\) 的 border 。

周期

对于字符串 \(s\) 和整数 \(q(1\le q\le |S|)\) ,满足 \(s[i]=s[i+p],\forall i \in [1,|s|-p]\) ,则 \(p\) 就是 \(s\) 的周期。

Weak Periodicity Lemma

如果 \(p\) 和 \(q\) 是字符串 \(s\) 的周期,则 \(gcd(p,q)\) 也是字符串 \(s\) 的周期。

border 的结构

引理 1

字符串 \(s\) 的所有长度不小于 \(\frac{|s|}{2}\) 的 border 组成一个等差数列。

证明

设 \(s\) 的最大 border 长度为 \(n-p(p\le \frac{|s|}{2})\) ,另外的某一个 border 的长度为 \(n-q(q\le \frac{|s|}{2})\) 。

则 \(p,q\) 均为 \(s\) 的周期,且 \(p\) 为最小周期(当然可能 \(p=0\) )。

那么 \(gcd(p,q)\) 也是 \(s\) 的周期,所以 \(gcd(p,q)\ge p\Rightarrow gcd(p,q)=p\) ,显然可以得到 \(p|q\) 。

推广

将 \(s[1\cdots n]\) 的所有 border 按照长度 \(x\) 分类:

\(x\in [1,2),[2,4),\cdots ,[2^{k-1},2^k),[2^k,n)\) 。

分开考虑每段区间,与上述的证明类似,可以知道,在每一个区间内的 border 长度均构成等差数列。

于是可以得到:字符串 border 排序后可以分成 \(O(log_2|S|)\) 段,每一段都是一个等差数列

Palindrome Series

考虑一个回文串 \(S\) 的后缀 \(T\) ,则有: \(T\) 是回文串与 \(T\) 是 \(S\) 的 border 等价。再结合上面的 Border Series 结构,即可得到一个推论:一个回文串的所有回文后缀可以表示为 \(O(log_2|S|)\) 段等差数列

我们可以设法对每段等差数列进行维护,就可以 \(O(log_2|S|)\) 枚举所有回文后缀,这就是 Palindrome Series 做的事情。

PAM

对于回文自动机,对于每一个结点的状态至少要有的信息:

  • len 当前状态表示的回文串长度;
  • fail 当前状态的 fail 指针,即当前表示的回文串的最长 border ;
  • diff 当前状态和他最大 border 长度的差,即所在的等差数列的公差;
  • anc border 差相等的等差数列所在的首状态,即从当前状态顺着 fail 走,保证 diff 值都相同,最终能走到的点。

例题

A – Codeforces 932 G

Palindrome Partition

题解

【Codeforces932G】Palindrome Partition

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 118,805

Categories

Archive

Comments