#回文自动机#loj 141 回文子串
题目给定一个字符串 \(s\) 以及 \(Q\) 个操作。您需要编写一个程序以支持下列几种操作：
[*]在字符串 \(s\) 的末尾添加一个字符串；
[*]在字符串 \(s\) 的前端添加一个字符串的 反序；
[*]查询字符串 \(s\) 的所有非空回文子串的数量。
\(s\) 的两个子串视为不同，当且仅当这两个子串的长度不同或者这两个子串在 \(s\) 中的起始位置不同。
\(s\) 的反序字符串定义为将 \(s\) 中前后对称位置的字符两两对调位置后形成的字符串。
分析
维护回文自动机，每次答案会增加 dep，然而涉及到了两头的添加，
此时就要维护 lst 表示尾部/头部的 lst，此时 fail 仍然表示最长前后缀，
只是当 len 为字符串总长度时另一个 lst 也要等于这个 lst
代码
#include #include #include using namespace std;const int N=1200011; long long ans;int rev,n,L,R,m,Q; char s;struct PAM{ int trie,fail,len,dep,diff,slink,lst,cnt; void BUILD(){fail=cnt=1,len=-1;} int getf(int n,int now){for (;s+1)*(rev?-1:1)]^s;now=fail); return now;} void Insert(int n){ int Lst=getf(n,lst); if (!trie-97]){ int now=++cnt; len=len+2; fail=trie)]-97]; trie-97]=now; dep=dep]+1; diff=len-len]; if (diff==diff]) slink=slink]; else slink=fail; } lst=trie-97]; if (len]==R-L+1) lst=lst; ans+=dep]; }}pam;int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); pam.BUILD(); string str; cin>>str,n=str.length(); L=400001,R=L-1; for (int i=1;i>Q;Q;--Q){ int opt; cin>>opt; switch (opt){ case 1:{ cin>>str,m=str.length(); for (int i=1;i>str,m=str.length(); for (int i=1;i
页:
[1]