序列自动机

• OI Wiki: https://oi-wiki.org/string/seq-automaton/

题目	难度
$727. 最小窗口子序列	困难	子序列自动机
792. 匹配子序列的单词数	中等	子序列自动机
2014. 重复 K 次的最长子序列	困难	子序列自动机
CF91A	rating 1500	子序列自动机
CF1845C	rating 1400	子序列自动机

定义

$727. 最小窗口子序列

import java.util.Arrays;

public class Solution727 {
    public String minWindow(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();

        int[] pos = new int[26];
        Arrays.fill(pos, n);

        // nxt[i][j] 表示 s[i] 右侧最近的字母 j 的位置
        int[][] nxt = new int[n][26];
        for (int i = n - 1; i >= 0; i--) {
            nxt[i] = pos.clone();
            pos[s1.charAt(i) - 'a'] = i;
        }

        String ans = "";
        for (int i0 = 0; i0 < n; i0++) {
            // 遍历所有 s 中的 t[0]
            if (s1.charAt(i0) == s2.charAt(0)) {
                int i = i0;
                // 匹配 t 中的字符
                for (int j = 1; j < m; j++) {
                    i = nxt[i][s2.charAt(j) - 'a'];
                    if (i == n) {
                        return ans;
                    }
                }
                String w = s1.substring(i0, i + 1);
                if (ans.equals("") || w.length() < ans.length()) {
                    ans = w;
                }
            }
        }
        return ans;
    }
}

792. 匹配子序列的单词数

import java.util.Arrays;

public class Solution792 {
    public int numMatchingSubseq(String s, String[] words) {
        int n = s.length();

        // 子序列自动机
        int[] pos = new int[26];
        Arrays.fill(pos, -1);
        int[][] nxt = new int[n + 1][26];
//        nxt[n] = pos.clone();
        System.arraycopy(pos, 0, nxt[n], 0, 26);
        for (int i = n - 1; i >= 0; i--) {
            pos[s.charAt(i) - 'a'] = i;
//            nxt[i] = pos.clone();
            System.arraycopy(pos, 0, nxt[i], 0, 26);
        }

        int ans = words.length;
        for (String word : words) {
            int pre = 0;
            for (int j = 0; j < word.length(); j++) {
                pre = nxt[pre][word.charAt(j) - 'a'];
                if (pre < 0) {
                    ans--;
                    break;
                }
                pre++;
            }
        }
        return ans;
    }
}

CF1845C

import java.nio.charset.StandardCharsets;
import java.util.Arrays;
import java.util.Scanner;

public class CF1845C {
    static String s, l, r;
    static int m;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in, StandardCharsets.UTF_8);
        int t = scanner.nextInt();
        while (t-- > 0) {
            s = scanner.next();
            m = scanner.nextInt();
            l = scanner.next();
            r = scanner.next();
            System.out.println(solve());
        }
    }

    // https://codeforces.com/contest/1845/submission/211453965
    private static String solve() {
        int n = s.length();

        // 子序列自动机
        // 预处理 s[i] 下一个 '0'~'9' 出现的位置
        int[][] next = new int[n + 1][10];
        Arrays.fill(next[n], n);
        for (int i = n - 1; i >= 0; i--) {
            next[i] = next[i + 1].clone();
            next[i][s.charAt(i) - '0'] = i;
        }

        int cur = -1;
        for (int i = 0; i < m && cur < n; i++) {
            int nxt = 0;
            for (int j = l.charAt(i) - '0'; j <= r.charAt(i) - '0'; j++) {
                nxt = Math.max(nxt, next[cur + 1][j]);
            }
            cur = nxt;
        }
        return cur == n ? "YES" : "NO";
    }
}

（全文完）