[JSOI2013] 快乐的 JYY - 回文自动机,DFS

标签：insert   include   als   pam   回文   ast   oid   code   for   

#include 
#define Sigma 30
#define MAXN 500010
#define int long long
using namespace std ;
int n, m, ans ; char s[MAXN], t[MAXN] ;
struct PAM{
    int rt0, rt1, last, sz, f[MAXN], ch[MAXN][Sigma], fail[MAXN], len[MAXN] ;
    void Init(){
        sz = -1, rt0 = ++ sz, rt1 = ++ sz ;
        fail[rt0] = fail[rt1] = rt1, len[rt0] = 0, len[rt1] = -1, last = rt0 ;
    }
    PAM(){Init();}
    void Insert(int x, int p, char *s){
        int u = last ;
        while (s[p] != s[p - len[u] - 1]) u = fail[u] ;
        if (!ch[u][x]){
            int newq = ++ sz, fa = fail[u] ;
            while (s[p] != s[p - len[fa] - 1]) fa = fail[fa] ;
            fail[newq] = ch[fa][x], ch[u][x] = newq, len[newq] = len[u] + 2 ;
        }
        last = ch[u][x], f[last] ++ ;
    }
    void Solve() {
        for(int i=sz;i;--i) f[fail[i]] += f[i];
    }
}p,q;
void dfs(int x,int y) {
    if(x+y>2) ans += p.f[x]*q.f[y];
    for(int i=1;i>s+1>>t+1;
    n=strlen(s+1);
    m=strlen(t+1);
    for(int i=1;i

[JSOI2013] 快乐的 JYY - 回文自动机,DFS

标签：insert   include   als   pam   回文   ast   oid   code   for   

原文地址：https://www.cnblogs.com/mollnn/p/12252850.html