【题解】

暴力能AC，乱写艹标程

序列自动机：

# include <stdio.h>
# include <string.h>
using namespace std;

const int M=120000;
struct segAM {
	int ch[M][66], head[62], next[M], tot, root;
	segAM() {
		tot = root = 1;
		for (int i=0; i<60; ++i) head[i] = root;
	}
	inline void insert(char c) {
		++tot;
		next[tot] = head[c];
		for (int i=0; i<60; ++i) 
			for (int j=head[i]; j&&!ch[j][c]; j=next[j]) ch[j][c] = tot;
		head[c] = tot;
	}
}SA, SB;

typedef long long ll;
ll dp[3010][3010];


inline ll get(int a, int b) {
	if (a==0 || b==0) return 0;
	if (dp[a][b]>=0) return dp[a][b];
	long long ans = 1;
	for (int i=0; i<60; ++i) ans += get(SA.ch[a][i], SB.ch[b][i]);
	return dp[a][b] = ans;
}

int fs[M], gs[M];
char s[M];
inline void get2(int a, int b, int step) {
	if(a==0 || b==0) return;
	s[step] = 0; printf("%s\n", s);
	for (int i=0; i<60; ++i) {
		s[step] = fs[i];
		get2(SA.ch[a][i], SB.ch[b][i], step+1);
	}
}
int k, n, m; char x[M], y[M];
int main() {
	for (int i='A'; i<='Z'; ++i) gs[i]=i-'A', fs[i-'A']=i;
	for (int i='a'; i<='z'; ++i) gs[i]=i-'a'+26, fs[i-'a'+26]=i;
	scanf("%d%d", &n, &m);
	scanf("%s%s", x, y);
	scanf("%d", &k);
	for (int i=0; i<n; ++i) SA.insert(gs[x[i]]);
	for (int i=0; i<m; ++i) SB.insert(gs[y[i]]);
	if(k==1) get2(1, 1, 0);
	memset(dp, -1, sizeof(dp));
	printf("%lld\n", get(1, 1));
	return 0;
}

暴力：

# include <stdio.h>
# include <string.h>
# include <algorithm>
using namespace std;
int m,n;
const int M=4040,ZF=53,DFSN=400010;
typedef long long ll;
const ll F=1e8, ZFBase=1LL<<52;
struct bign {
	ll a[510],l;
	void pr() {
		printf("%d",a[l-1]);
		for (int i=l-2; i>=0; --i) printf("%08d",a[i]);
		printf("\n");
	}
}*f[M][M], v[DFSN], *vv = v;
char a[M], b[M];
int c[M][53], d[M][53];
int k;
ll havesame1[M],havesame2[M];

inline char get(int s) {
	if (s<=25) return s+'A';
	else return (s-26)+'a';
}

inline void inset(ll& a, int j) {
	a = a | (1LL<<j);
}

inline void outset(ll &a, int j) {
	a = a - (1LL<<j);
}


char str[M];
int counts = 0;

inline void dfs(int step,int i,int j) {
	puts(str);
	counts++;
	ll s=havesame1[i+1]&havesame2[j+1];
	while(s) {
		int zero = __builtin_ctzll(s);
		str[step] = get(zero);
		dfs(step+1, c[i+1][zero], d[j+1][zero]);
		outset(s, zero);
	}
	if(step>=0) str[step]=0;
}

inline bign* dfs2(int i,int j) {
	if(f[i][j]) return f[i][j];
	vv->a[0] = 1;
	vv->l = 1;
	f[i][j] = vv++;
	bign* a = f[i][j];
	ll s=havesame1[i+1]&havesame2[j+1];
	while(s) {
		int zero = __builtin_ctzll(s);
		bign *b = dfs2(c[i+1][zero], d[j+1][zero]);
		int ls=0;
		if(a->l > b->l) ls = a->l;
		else ls = b->l;
		ll change = 0;
		for (int k=0; k<ls; ++k) {
			if(k < a->l) change += a->a[k];
			if(k < b->l) change += b->a[k];
			a -> a[k] = change%F;
			change /= F;
		}
		if(change) a->a[ls] = change, ls++;
		a->l = ls;
		outset(s, zero);
	}
	return f[i][j];
}

int main() {
	freopen("allcs.in","r",stdin);
	freopen("allcs.out","w",stdout);
	scanf("%d%d",&m,&n);
	scanf("%s%s%d",a+1,b+1,&k);
	for (int i=0; i<=51; ++i) c[m+1][i]=m+1,d[n+1][i]=n+1;
	for (int i=m; i>=1; --i) 
		for (int j=0; j<=51; ++j) {
			char strn = get(j);
			if(a[i]==strn) c[i][j]=i;
			else c[i][j]=c[i+1][j];
			if(c[i][j]!=m+1) inset(havesame1[i], j);
		}
	for (int i=n; i>=1; --i) 
		for (int j=0; j<=51; ++j) {
			char strn = get(j);
			if(b[i]==strn) d[i][j]=i;
			else d[i][j]=d[i+1][j];
			if(d[i][j]!=n+1) inset(havesame2[i], j);
		}
	/*
	for (int i=1;i<=m;++i,printf("\n"))
		for (int j=0;j<51;++j)
			printf("%d ",c[i][j]);
	printf("===\n");
	for (int i=1;i<=n;++i,printf("\n"))
		for (int j=0;j<51;++j)
			printf("%d ",d[i][j]);
	*/
	if(k) {
		dfs(0,0,0);
		printf("%d\n", counts);
	} else {
		dfs2(0,0)->pr();
	}
	fclose(stdin);
	fclose(stdout);
	return 0;	
}