序列自动机

发表于 | 分类于 ，
本文字数： 5.1k

题目

392. 判断子序列

题意

  1. 给定字符串\(s\)、\(t\)，判断\(s\)是否为\(t\)的子序列；

  2. 给定字符串\(s_1,s_2,\dots\)，依次判断他们是否是\(t\)的子序列；

数据范围

\(0\leq |s| \leq 100, 0\leq |t| \leq 10000\)

题解

对于第一个问题，显然暴力就行；

对于第二个问题；注意到，如果对于\(s[i]\)和\(t[j]\)相同，那么我们只能在\(t\)中位置\(j\)之后找与\(s[i+1]\)相同的字符，并且我们应该贪心的，在\(t\)中位置\(j\)后面的字符中，找尽可能在前面的与\(s[i+1]\)匹配的字符，以此让后面的字符有更多机会匹配成功；

这就需要我们统计，第\(i\)个字符后面的第一个a ~ z，这就需要通过序列自动机来实现，本质上也就是\(dp\)；

code

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

class Solution {
public:
    bool isSubsequence(string s, string t) {
        if (s == "") return 1;
        if (t == "") return 0;
        int f[10004][30];
        int ts = t.size();
        int ss = s.size();
        memset(f, -1, sizeof(f));
        // 序列自动机
        for (int i = ts - 1; i>=0; i--) {
            for (int j = 0; j < 26; j++){
                f[i][j] = f[i + 1][j];
            }
            f[i][t[i] - 'a'] = i;
        }
        
        int l = 0;
        for (int i = 0; i < ss; i++)
            if (f[l][s[i] - 'a'] == -1)return 0;
            else l = f[l][s[i] - 'a'] + 1;
        return 1;
    }
};