题目描述：
题解：
序列自动机（？）+高精+普及dp。
这个是猫老师的序列自动机（字符串从1开始）：
void sol(char *s,int n,int t[N][])
{
memset(t[n],-,sizeof(t[n]));
for(int i=n-;i>=;i--)
{
memcpy(t[i],t[i+],sizeof(t[i]));
t[i][ci(s[i+])] = i+;
}
}
序列自动机
$t$数组记录在位置$i$的后面加字符$j$能到达的最左边的位置。
对于这道题，直接对两个串构造序列自动机，然后爆搜即可。
$k=1$没啥好说的，$k=0$高精压18位。
时间复杂度$O(n^2)$。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = ;
const ll M = 1000000000000000000ll;
struct bignum
{
ll a[];//
int len;
void operator += (const bignum&x)
{
int mx = max(len,x.len);
for(int i=;i<mx;i++)
{
a[i]+=x.a[i];
if(a[i]>=M)a[i+]+=a[i]/M,a[i]%=M;
}
while(a[len])len++;
}
void operator += (const ll&x)
{
a[]+=x;
for(int i=;a[i]>=M;i++)a[i+]+=a[i]/M,a[i]%=M;
while(a[len])len++;
}
void write()
{
if(!len){puts("");return ;}
printf("%lld",a[len-]);
for(int i=len-;i>=;i--)
printf("%018lld",a[i]);
puts("");
}
}dp[];
int n,m,k,t1[N][],t2[N][],id[N][N],tot=,ans=;
char s1[N],s2[N];
int ci(char ch)
{
if(ch>='A'&&ch<='Z')return ch-'A';
return ch-'a'+;
}
char ic(int i)
{
if(i<)return 'A'+i;
return 'a'+i-;
}
void sol(char *s,int n,int t[N][])
{
memset(t[n],-,sizeof(t[n]));
for(int i=n-;i>=;i--)
{
memcpy(t[i],t[i+],sizeof(t[i]));
t[i][ci(s[i+])] = i+;
}
}
int tl;
char now[N];
void dfs1(int a,int b)
{
for(int i=;i<=tl;i++)
putchar(now[i]);
putchar('\n');
ans++;
for(int i=;i<;i++)if(~t1[a][i]&&~t2[b][i])
{
now[++tl] = ic(i);
dfs1(t1[a][i],t2[b][i]);
tl--;
}
}
void dfs2(int a,int b)
{
if(id[a][b])return ;
id[a][b]=++tot;
dp[tot]+=;
for(int i=;i<;i++)if(~t1[a][i]&&~t2[b][i])
{
dfs2(t1[a][i],t2[b][i]);
dp[id[a][b]]+=dp[id[t1[a][i]][t2[b][i]]];
}
} int main()
{
// freopen("tt.in","r",stdin);
scanf("%d%d%s%s%d",&m,&n,s1+,s2+,&k);
sol(s1,m,t1),sol(s2,n,t2);
if(k==){dfs1(,);printf("%d\n",ans);return ;}
dfs2(,);dp[id[][]].write();
return ;
}