回文自动机PAM 例题

洛谷 P4555 最长双回文串

输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。

分析：构造两个回文自动机PAM，把串s正反分别跑一遍，然后枚举分割点就行了。
很巧妙地一个作法，枚举分割点即可。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e5+5;
int len;
char s[maxn];
typedef struct PAM{
    int Trie[maxn][27],fail[maxn],size,Len[maxn],last,mp[maxn];
    int ans;
    PAM(){
        fail[0] = fail[1] = 1;
        Len[0] = 0,Len[1] = -1;
        size = 1;   last = 1;
        ans = 0;
    }
    void Insert(char ch,int idx){
        while (s[idx-1-Len[last]]!=s[idx])  last = fail[last];
        if (!Trie[last][ch-'a'+1]){
            int v = fail[last];
            while (s[idx-Len[v]-1]!=s[idx]) v = fail[v];
            fail[++size] = Trie[v][ch-'a'+1];
            Trie[last][ch-'a'+1] = size;
            Len[size] = Len[last] + 2;
        }
        last = Trie[last][ch-'a'+1];
        mp[idx] = last;
    }
    void Build(char *s,int len){
        for (int i=1;i<=len;i++){
            Insert(s[i],i);
        }
        return;
    }
}PAM;
PAM A,B;
int ans = 0;
void solve(){
    for (int i=1;i<len;i++)
        ans = max(ans,A.Len[A.mp[i]]+B.Len[B.mp[len-i]]);
    printf ("%d",ans);
    return;
}
int main(){
    scanf ("%s",s+1);
    len = strlen(s+1);
    A.Build(s,len);
    for (int i=1;i<=len/2;i++)  swap(s[i],s[len-i+1]);
    B.Build(s,len);
    solve();
    return 0;
}

洛谷P6216 回文匹配

给定两字符串s1, s2.求s2在(s1中的所有奇数长度回文中)的出现次数之和。奇数回文有相同的，按多次计算。
PAM+KMP+TOPO
数据量巨大，出题人估计想卡PAM，，，但我还是强行A了
也挺简单，，基本步骤：
1.对s1构建PAM，每个结点对应的回文串的出现次数用TOPO解决。
2.s2在每个奇数回文中的出现次数用KMP解决。
然后最后答案，就是(每个奇数回文的出现次数乘以s2在该奇数回文中的出现次数)之和了。
其中求第2步时，应先在s1上跑一遍KMP，求出区间[1,i]内s2的出现次数(即前缀和)，然后对PAM中的每个结点，判断其对应的回文在s1中的区间，直接O(1)求出s2在该回文中的出现次数。
求前缀和，s2在s1中出现的终结点记为s2的出现位置。
时间复杂度O(n+m)，常数很大，基本把时间复杂度向上翻了一个数量级。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = 3e6+5;
typedef struct PAM{
    int Trie[maxn][27],fail[maxn],size,last,Len[maxn],in[maxn];
    int times[maxn];
    int len1,len2;
    char s1[maxn],s2[maxn];
    int Next[maxn],mark[maxn];               //mark标记结点在母串s1中的位置
    ll dp[maxn];
    ll ans,mod;
    PAM(){
        last = size = 1;
        Len[0] = 0,Len[1] = -1;
        fail[0] = fail[1] = 1;
        ans = 0;
        mod = pow(2, 32);
    }
    void Insert(char ch,int idx){
        while (s1[idx-Len[last]-1]!=s1[idx])  last = fail[last];
        if (!Trie[last][ch-'a'+1]){
            int v = fail[last];
            while (s1[idx-Len[v]-1]!=s1[idx])   v = fail[v];
            fail[++size] = Trie[v][ch-'a'+1];
            in[fail[size]]++;
            Trie[last][ch-'a'+1] = size;
            Len[size] = Len[last] + 2;
        }
        times[Trie[last][ch-'a'+1]]++;
        last = Trie[last][ch-'a'+1];
        if (!mark[last])    mark[last] = idx;
    }
    void Build(){
        for (int i=1;i<=len1;i++)
            Insert(s1[i],i);
        topu();
        printf ("%lld", ans);
        return;
    }
    void KMP(){
        for (int i=2,j=0;i<=len2;i++){
            while (j && s2[i]!=s2[j+1])    j = Next[j];
            if (s2[i]==s2[j+1])   j++;
            Next[i] = j;
        }
        for (int i=1,j=0;i<=len1;i++){
            while (j && s1[i]!=s2[j+1])  j = Next[j];
            if (s1[i]==s2[j+1])  j++;
            dp[i] = dp[i-1];
            if (j==len2){
                dp[i]++;
                j = Next[j];
            }
        }
        return;
    }
    void topu(){
        queue<int>  q;
        for (int i=2;i<=size;i++)   if (in[i]==0)
            q.push(i);
        while (!q.empty()){
            int tmp = q.front();    q.pop();
            if (Len[tmp]&1)                     //拓扑排序进行时，统计答案。
                ans = (ans+GetAns(mark[tmp], Len[tmp])*times[tmp])%mod;
            times[fail[tmp]] += times[tmp];
            in[fail[tmp]]--;
            if (in[fail[tmp]]==0)
                q.push(fail[tmp]);
        }
        return;
    }
    ll GetAns(int idx, int len){
        int l = idx-len+1 + len2-1-1;
        if (l>idx)  return 0;
        return dp[idx]-dp[l];
    }
}PAM;
PAM P;
int main(){
    scanf ("%d %d",&P.len1,&P.len2);
    scanf ("%s %s",P.s1+1,P.s2+1);
    P.KMP();
    P.Build();
    return 0;
}