子序列自动机创建及算法

#include<iostream>
#include<string>
using namespace std;
const int MAXN = 1e5+10;
string a;
int Next[MAXN][26];
void getNext(string &str){    //创建后缀自动机 
    int len = str.size() - 1;    
    for(int j = 0; j < 26; j++)    Next[len][j] = len + 1;        
    for(int i = len; i >= 1; i--){
        for(int j = 0; j < 26; j++)    Next[i-1][j] = Next[i][j];            
        if(i)    Next[i-1][str[i]-'a'] = i;
    }
}

int f[maxn];
int dfs(int x){//求子序列个数,调用dfs(0)
    if(f[x]) return f[x];
    for(r int i=1;i<=a;i++)
        if(Next[x][i]) f[x]+=dfs(Next[x][i]);
    return ++f[x];
}


int f[maxn][maxn];
int dfs(int x,int y){
//公共子序列个数,调用dfs(0, 0)表示目前字符是串1的第x位,串2的第y位
//Next1和Next2是两个串的子序列自动机
    if(f[x][y]) return f[x][y];
    for(nt i=1;i<=a;i++)
        if(Next1x][i]&&Next2y][i]) f[x][y]+=dfs(Next1x][i],Next2y][i]);
    return ++f[x][y];
}



int f[maxn][maxn];
int dfs(int x,int y){
    //回文子序列个数,调用dfs(0, 0) 
    if(f[x][y]) return f[x][y];//记忆化
    for(int i=1;i<=26;i++)
        if(next1[x][i]&&next2[y][i])
        {
            if(next1[x][i]+next2[y][i]>n+1) continue;//x+y>n+1,状态不合法,不进行统计
            if(next1[x][i]+next2[y][i]<n+1) f[x][y]++;
            //满足x+y=n+1的奇串不会被漏掉,其他奇串需要特别统计
            f[x][y]=(f[x][y]+dfs(next1[x][i],next2[y][i]))%mod;
        }
    return ++f[x][y];
}