结构
和其他自动机类似，由转移边 \(t\) 和后缀链接 \(fail\) 构成
每个结点 \(u\) 代表一个本质不同的回文子串，\(len[u]\) 表示该串长度，\(t[u,i]\) 指向在两端加 \(i\) 得到的回文串，\(fail[u]\) 指向最长回文后缀
建树
由于回文串分为奇数长度和偶数长度，所以 PAM 事实上是两棵树
初始状态为奇根 \(1\) 和偶根 \(0\)，代表长度分别为 \(-1,0\) 的空回文串，偶根的 \(fail\) 指向奇根
增量构造。设原来最长回文后缀为结点 \(lst\)，插入字符 \(s[n]\) 时从 \(lst\) 开始跳 \(fail\) 至 \(s[n]=s[n-len[u]-1]\)，\(t[u,s[n]]\) 即为当前最长回文后缀对应的结点。不存在就新建 \(v\)，从 \(fail[u]\) 开始跳 \(fail\) 至 \(s[n]=s[n-len[x]-1]\)，\(fail[v]\) 即为 \(t[x,s[n]]\)