算法

(后缀自动机，序列自动机) $O(n^2)$

1. 对字符串 $b$ 构造后缀自动机（接受子串）和序列自动机（接受子序列）。
2. 对于问题 1 和 2，枚举字符串 $a$ 的每个子串，枚举过程中将子串输入到 $b$ 的自动机中识别。当自动机拒绝时，更新答案。
3. 对于问题 3 和 4，通过动态规划求解。
   • 设状态 $f(i, j)$ 为考察了字符串 $a$ 的前 $i$ 个字符，通过 $a$ 的第 $i$ 个字符转移到自动机状态 $j$ 时，与字符串 $a$ 以 $i$ 结尾的子序列的最短匹配长度。其中 $i$ 的有效下标从 $1$ 开始。
   • 初始时，$f(0, 0) = 0$，其余为正无穷。
   • 转移时
     • $f(i, j) = \min(f(i, j), f(i - 1, j))$，表示忽略字符串 $a$ 的第 $i$ 个字符。
     • 如果某个状态 $j$ 没有字符 $a(i)$ 的转移，则可以更新答案 $ans = \min(ans, f(i - 1, j) + 1)$，因为此时以字符 $a(i)$ 结尾的子序列一定不会被自动机接受。
     • 否则，假设自动机状态 $j_0$ 通过字符 $a(i)$ 到达的状态为 $p$，则转移 $f(i, p) = \min(f(i, p), f(i - 1, j) + 1)$，表示以字符 $a(i)$ 结尾的子序列可以到达状态 $p$。

时间复杂度

• 假设字符集的大小为常数，构造自动机的时间复杂度均为 $O(n)$。
• 问题 1 和 2 需要枚举 $a$ 的子串，每个子串均摊仅需常数的时间判定。
• 问题 3 和 4 的动态规划的状态数为 $O(n^2)$，转移时间为常数。
• 故总时间复杂度为 $O(n^2)$。

空间复杂度

• 假设字符集的大小为常数，自动机的占用空间为 $O(n)$。
• 问题 3 和 4 的动态规划的状态数为 $O(n^2)$。
• 故总空间复杂度为 $O(n^2)$。动态规划可使用滚动数组或倒序递推的方式将空间降为 $O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 2010;

struct SamNode {
    int len, link;
    int nxt[26];
    SamNode() {
        memset(nxt, -1, sizeof(nxt));
    }
};


class Sam {
public:
    SamNode st[N * 2];
    int rt, sz;

    Sam(char *s) {
        int len = strlen(s);

        init();
        for (int i = 0; i < len; i++)
            extend(s[i] - 'a');
    }

private:
    int last;

    void init() {
        st[0].len = 0;
        st[0].link = -1;
        sz = 1;
        last = 0;
        rt = 0;
    }

    void extend(int c) {
        int cur = sz++;
        st[cur].len = st[last].len + 1;
        int p = last;
        while (p != -1 && st[p].nxt[c] == -1) {
            st[p].nxt[c] = cur;
            p = st[p].link;
        }

        if (p == -1) {
            st[cur].link = 0;
        } else {
            int q = st[p].nxt[c];
            if (st[q].len == st[p].len + 1) {
                st[cur].link = q;
            } else {
                int clone = sz++;
                st[clone].len = st[p].len + 1;
                st[clone].link = st[q].link;
                memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
                while (p != -1 && st[p].nxt[c] == q) {
                    st[p].nxt[c] = clone;
                    p = st[p].link;
                }
                st[q].link = st[cur].link = clone;
            }
        }
        last = cur;
    }
};

struct SeqNode {
    int nxt[26];
    SeqNode() {
        memset(nxt, -1, sizeof(nxt));
    }
};

class Seq {
public:
    SeqNode st[N];
    int sz, rt;

    Seq(char *s) {
        int nxt[26];
        memset(nxt, -1, sizeof(nxt));

        int last = sz++;
        int len = strlen(s);

        for (int i = len - 1; i >= 0; i--) {
            nxt[s[i] - 'a'] = last;

            int cur = sz++;
            memcpy(st[cur].nxt, nxt, sizeof(nxt));
            last = cur;
        }
        rt = sz - 1;
    }
};

int f[N][2 * N];

void solve_1(char *a, const Sam &b) {
    int n = strlen(a);
    int ans = n + 1;

    for (int i = 0; i < n; i++) {
        int p = b.rt;
        for (int j = i; j < n; j++) {
            if (j - i + 1 >= ans)
                break;

            int c = a[j] - 'a';
            if (b.st[p].nxt[c] == -1) {
                ans = j - i + 1;
                break;
            }
            p = b.st[p].nxt[c];
        }
    }
    printf("%d\n", ans == n + 1 ? -1 : ans);
}

void solve_2(char *a, const Seq &b) {
    int n = strlen(a);
    int ans = n + 1;

    for (int i = 0; i < n; i++) {
        int p = b.rt;
        for (int j = i; j < n; j++) {
            if (j - i + 1 >= ans)
                break;

            int c = a[j] - 'a';
            if (b.st[p].nxt[c] == -1) {
                ans = j - i + 1;
                break;
            }
            p = b.st[p].nxt[c];
        }
    }
    printf("%d\n", ans == n + 1 ? -1 : ans);
}

void solve_3(char *a, const Sam &b) {
    memset(f, 0x3f, sizeof(f));
    int n = strlen(a);
    f[0][b.rt] = 0;

    int ans = n + 1;
    for (int i = 1; i <= n; i++) {
        int c = a[i - 1] - 'a';

        for (int j = 0; j < b.sz; j++) {
            f[i][j] = min(f[i][j], f[i - 1][j]);

            int p = b.st[j].nxt[c];
            if (p != -1) f[i][p] = min(f[i][p], f[i - 1][j] + 1);
            else ans = min(ans, f[i - 1][j] + 1);
        }
    }

    printf("%d\n", ans == n + 1 ? -1 : ans);
}

void solve_4(char *a, const Seq &b) {
    memset(f, 0x3f, sizeof(f));
    int n = strlen(a);
    f[0][b.rt] = 0;

    int ans = n + 1;
    for (int i = 1; i <= n; i++) {
        int c = a[i - 1] - 'a';
        for (int j = 0; j < b.sz; j++) {
            f[i][j] = min(f[i][j], f[i - 1][j]);

            int p = b.st[j].nxt[c];
            if (p != -1) f[i][p] = min(f[i][p], f[i - 1][j] + 1);
            else ans = min(ans, f[i - 1][j] + 1);
        }
    }

    printf("%d\n", ans == n + 1 ? -1 : ans);
}


int main() {
    char a[N], b[N];
    scanf("%s%s", a, b);
    Sam sam_b(b);
    Seq seq_b(b);

    solve_1(a, sam_b);
    solve_2(a, seq_b);
    solve_3(a, sam_b);
    solve_4(a, seq_b);

    return 0;
}