#回文自动机#loj 141 回文子串

题目

给定一个字符串 \(s\) 以及 \(Q\) 个操作。您需要编写一个程序以支持下列几种操作：

• 在字符串 \(s\) 的末尾添加一个字符串；
  
• 在字符串 \(s\) 的前端添加一个字符串的 反序；
  
• 查询字符串 \(s\) 的所有非空回文子串的数量。
  

\(s\) 的两个子串视为不同，当且仅当这两个子串的长度不同或者这两个子串在 \(s\) 中的起始位置不同。
\(s\) 的反序字符串定义为将 \(s\) 中前后对称位置的字符两两对调位置后形成的字符串。
分析

维护回文自动机，每次答案会增加 dep[lst]，然而涉及到了两头的添加，
此时就要维护 lst[0/1] 表示尾部/头部的 lst，此时 fail 仍然表示最长前后缀，
只是当 len[lst] 为字符串总长度时另一个 lst 也要等于这个 lst
代码

[code]#include #include #include using namespace std;const int N=1200011; long long ans;int rev,n,L,R,m,Q; char s[N];struct PAM{    int trie[N][26],fail[N],len[N],dep[N],diff[N],slink[N],lst[2],cnt;    void BUILD(){fail[0]=cnt=1,len[1]=-1;}    int getf(int n,int now){for (;s[n-(len[now]+1)*(rev?-1:1)]^s[n];now=fail[now]); return now;}    void Insert(int n){        int Lst=getf(n,lst[rev]);        if (!trie[Lst][s[n]-97]){            int now=++cnt;            len[now]=len[Lst]+2;            fail[now]=trie[getf(n,fail[Lst])][s[n]-97];            trie[Lst][s[n]-97]=now;            dep[now]=dep[fail[now]]+1;                        diff[now]=len[now]-len[fail[now]];            if (diff[now]==diff[fail[now]]) slink[now]=slink[fail[now]];                else slink[now]=fail[now];        }        lst[rev]=trie[Lst][s[n]-97];        if (len[lst[rev]]==R-L+1) lst[rev^1]=lst[rev];        ans+=dep[lst[rev]];    }}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