所谓回文自动机,就是一个能用来做回文问题的自动机。
Part 0. 待解决的问题
问一个串的本质不同回文串个数。
需要一个线形做法。
以下为 abbaabba 的回文自动机。
Part 1. 构造
考虑建一个树形结构。也就是回文树。
-
增量法构造,在 \(s[0\sim i-1]\) 的回文树增加一个 \(s[i]\),只会增加一个节点。
证明:考虑新产生的最长回文子串,所有新产生的回文串,都是最长回文子串的回文后缀。会发现这些新产生的都能一一对应翻转以后的前面插入过的短串。于是只会增加一个最新回文子串的节点。
于是本质不同回文子串的数目是 \(O(n)\) 的。
你会发现答案就是自动机点数 - 2.
- fail 指针
和 AC 自动机类似,它的 fail 指针对应最长可匹配的前后缀,PAM 的 fail 则定义为最长回文后缀的位置。
设 \(s[0\sim i-1]\) 的最长回文子串在 PAM 上的节点为 \(x\)。
我们考虑 \(i - 1 - len[x]\) 和 \(s[i]\) 是否匹配,如果匹配,我们就知道这个是最长的了。
考虑 \(s[i]\) 的最长回文子串是 \(s[i-len[i]+1\sim i]\),我们要求 \(s[i-len[i]+2 \sim i - 1]\) 是满足 \(s[i-1-len[x]] = s[i]\) 的最长回文子串,不然和新加的最长是他矛盾。
如果匹配了, 我们就让新节点的 fail 指向匹配的点 \(x\)。
- 细节
- fail[0] = 1,因为例如插入 \(aabbc\) 时,\(c\) 这个东西他是匹配不了啥的,但是能在奇数根连一条边,形如 \(1\to c\)。
如果是 \(aabbcc\),他是有机会形成 \(cc\) 这样的在 \(0\) 这个根的串,我们需要让他尝试一下。 - 要分类讨论新点是否存在,如果存在,那么直接让 当前节点去到 这个存在的点。(自动机嘛,维护的是当前 \(s[0\sim i]\) 的最长回文子串对应节点)。
不存在就新建节点。注意先更新 fail,方法是一直跳 \(fail[x]\) 的 fail,然后更新新点的 \(fail\)。然后设 \(siz[i]\) 表示自动机上 \(i\) 结尾的回文子串数目。
\(siz[x] = siz[fail[x]] + 1\),表示 \(x\) 比他最长回文后缀多一个回文子串。
要注意先更新 \(fail[x]\),在更新 fail[x] 的回文树fail[++idx] = tr[gfail(fail[y], i)][s[i] - 'a'], tr[y][s[i]-'a'] = idx;
。
这个很牛逼,插入 abbbc。比如说我在插入 \(b\) 时这么写。
插入 b 时,cur 在 2 号点,我们 fail[cur] 在 1 号店,\(y = gfail(fail[cur], i) = 1\),如果已经新建了 \(tr[y][s[i]]\),那么这时 fail[idx] 会指向 idx。(tr[y][s[i]] = idx)。
还有一个问题,为啥是从 fail[cur] 开始跳。
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef double db;
#define ep emplace_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define fout freopen("out.out","w",stdout);
#define fin freopen("in.in","r",stdin);
#define DE {cerr << "QAQ" << endl;}
#define dd(x) cerr << #x" = " << x << endl;
inline int read() {
int x=0, v=1,ch=getchar();
while('0'>ch||ch>'9') {
if(ch=='-') v=0;
ch=getchar();
}while('0'<=ch&&ch<='9') {
x=(x*10)+(ch^'0');
ch=getchar();
}return v?x:-x;
}
const int MAX = 5e5 + 5;
char s[MAX];
int fail[MAX],idx=1,tr[MAX][26],len[MAX],siz[MAX];
int gfail(int x,int i){
while(i-len[x]-1<0||s[i]!=s[i-len[x]-1]) x=fail[x];
return x;
}
signed main() {
fin;
scanf("%s", s);
int n=strlen(s);
fail[0]=1; len[1]=-1;
int x=0,lastans=0;
for(int i=0;i<n;++i){
if(i) s[i]=(s[i]-97+lastans)%26+97;
int y=gfail(x,i);
if(!tr[y][s[i]-'a']){
fail[++idx] = tr[gfail(fail[y], i)][s[i] - 'a'];
tr[y][s[i]-'a'] = idx;
len[idx]=len[y]+2;
siz[idx]=siz[fail[idx]]+1;
}
x=tr[y][s[i]-'a'];
// printf("%d ", lastans=siz[x]);
}
return 0;
}
标签:子串,自动机,串串,记录,最长,fail,define,PAM,回文
From: https://www.cnblogs.com/Lates/p/17250364.html