子序列自动机创建及算法
<pre><code class="language-cpp">#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];
}</code></pre>