#include <bits/stdc++.h>
using namespace std;
const int maxw = 20 + 1, mod = 1e9, maxn = 3010 + 1;
struct BigInt {
    int len, a[maxw];
    BigInt operator +(BigInt x) {
        int l1 = len, l2 = x.len, r[maxw], anslen = max(l1, l2), c1, c2;
        BigInt ans;
        c1 = anslen - l1, c2 = anslen - l2, r[0] = 0;

        //      for(int i=1;i<=l1;i++) cout<<a[i]<<" ";
        //      cout<<endl;
        //      for(int i=1;i<=l2;i++) cout<<x.a[i]<<" ";
        //      cout<<endl;
        for (int i = anslen; i; i--)
            r[i] = ((i - c1 > 0 ? a[i - c1] : 0) + (i - c2 > 0 ? x.a[i - c2] : 0));

        //      for(int i=1;i<=anslen;i++) cout<<r[i]<<" ";
        //      cout<<endl;
        for (int i = anslen; i; i--)
            r[i - 1] += (r[i] / mod), r[i] %= mod;

        if (r[0]) {
            for (int i = 1; i <= anslen + 1; i++)
                ans.a[i] = r[i - 1];

            ans.len = anslen + 1;
            return ans;
        }

        ans.len = anslen;

        for (int i = 1; i <= anslen + 1; i++)
            ans.a[i] = r[i];

        return ans;
    }
    void input() {
        string s;
        int l;
        cin >> s, l = s.size(), s = " " + s;
        int cnt = 0;

        for (int i = l; i >= 1; i -= 9) {
            int ch = 0;

            for (int j = max(1, i - 8); j <= i; j++)
                ch = (ch * 10) + (s[j] - '0');

            a[++cnt] = ch;
        }

        reverse(a + 1, a + cnt + 1);
        len = cnt;
    }
    void output() {
        for (int i = 1; i <= len; i++) {
            if (i > 1)
                printf("%09d", a[i]);
            else
                printf("%d", a[i]);
        }
    }
} f[maxn][maxn];
int n, m, nxt[2][maxn][52], q;
string s[2];
vector<string> ans;
char id(int x) {
    if (x < 26)
        return x + 'A';
    else
        return (x - 26) + 'a';
}
void dfs(int z1, int z2, string now) {
    if (z1 == n + 1 || z2 == m + 1)
        return ;

    now += s[0][z1], ans.push_back(now);

    for (int i = 0; i < 52; i++)
        dfs(nxt[0][z1][i], nxt[1][z2][i], now);
}
void solve() {
    cin >> n >> m >> s[0] >> s[1] >> q, s[0] = " " + s[0], s[1] = " " + s[1];

    for (int j = 0; j < 52; j++)
        nxt[0][n][j] = n + 1, nxt[1][m][j] = m + 1;

    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < 52; j++)
            nxt[0][i][j] = (s[0][i + 1] == id(j) ? i + 1 : nxt[0][i + 1][j]);
    }

    for (int i = m - 1; i >= 0; i--) {
        for (int j = 0; j < 52; j++)
            nxt[1][i][j] = (s[1][i + 1] == id(j) ? i + 1 : nxt[1][i + 1][j]);
    }

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            f[i][j].len = 1, f[i][j].a[1] = 0;

    f[0][0].len = 1, f[0][0].a[1] = 1;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int c = 0; c < 52; c++)
                f[nxt[0][i][c]][nxt[1][j][c]] = f[nxt[0][i][c]][nxt[1][j][c]] + f[i][j];
        }
    }

    BigInt res;
    res.len = 1, res.a[1] = 1;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            res = res + f[i][j];

    if (q) {
        dfs(0, 0, ""), sort(ans.begin(), ans.end());

        for (string st : ans) {
            for (char ch : st)
                if (ch != ' ')
                    cout << ch;

            cout << endl;
        }
    }

    res.output();
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;

    //  cin>>t;
    while (t--)
        solve();

    return 0;
}

我认为我的做法的时间复杂度是 $O(n^2)$ 并且有个 $20$ 常数的压位高精。请帮忙检查代码中有无可以卡空间和时间常数的地方，或者指出我的做法中有复杂度可优化的地方，或者建议我重构代码。