子序列自动机

判断s是不是t的子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool isSubsequence(string s, string t) {
    int m = t.size();
    vector<array<int, 26>> next(m + 2);
    t = " " + t;
    for (int i = m; i >= 1; i--) {
        for (int j = 0; j < 26; j++) {
            if (j == t[i] - 'a')
                next[i][j] = i + 1;
            else {
                next[i][j] = next[i + 1][j];
            }
        }
    }
    int p = 1;
    for (auto x : s) {
        p = next[p][x - 'a'];
    }
    if (p)
        return true;
    return false;
}

t最少由多少个个s的子序列拼接而成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int catseq(string s, string t) {
    int m = t.size();
    vector<array<int, 26>> next(m + 2);
    t = " " + t;
    for (int i = m; i >= 1; i--) {
        for (int j = 0; j < 26; j++) {
            if (j == t[i] - 'a')
                next[i][j] = i + 1;
            else {
                next[i][j] = next[i + 1][j];
            }
        }
    }
    int p = 1;
    int ans = 1;
    deb(s);
    for (auto x : s) {
        p = next[p][x - 'a'];
        deb(p);
        if (p == 0) {
            ans++;
            p = 1;
            p = next[p][x - 'a'];
            if (p == 0)
                return -1;
        }
    }

    return ans;
}
void solve() {
    string s, t;
    cin >> s >> t;
    cout << catseq(t, s) << endl;
}

本质不同子序列个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve() {
    int n;
    cin >> n;
    vector<int> dp(n + 1);  // 前i个数的不同子序列个数
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    map<int, int> mp;
    for (int i = 1; i <= n; i++) {
        if (mp.count(a[i]) == 0)
            dp[i] = 2 * dp[i - 1] + 1;
        else {
            int last = mp[a[i]];
            dp[i] = 2 * dp[i - 1] - dp[last - 1];
        }
        dp[i] %= mod;dp[i]+=mod;dp[i]%=mod;
        mp[a[i]] = i;
    }
    cout << dp[n] << endl;
}