算法——序列自动机

2025/3/1 23:52:55 来源：https://blog.csdn.net/oopxiajun2011/article/details/145915460 浏览: 次关键词：算法——序列自动机

序列自动机是一种用于高效判断一个字符串是否为另一个字符串的子序列的数据结构。其核心思想是通过预处理目标字符串，构建状态转移表，从而在O(1)时间复杂度下支持多次子序列查询。

1. 核心概念

子序列定义：若字符串sub可以通过删除字符串s中的某些字符（不改变顺序）得到，则称sub是s的子序列。例如，"ace"是"abcde"的子序列。
应用场景：文本编辑器中的快速输入提示、基因序列匹配、日志分析等。

2. 构建方法

预处理步骤：

初始化数组：创建一个二维数组next[i][c]，表示在字符串s的位置i之后，字符c下一次出现的位置。
逆序填充：从字符串末尾向前遍历，记录每个位置之后各字符的最近位置。

示例（以字符串s = "abcab"为例）：

位置: 0 1 2 3 4
字符: a b c a bnext数组（部分）：
next[0]['a'] = 3
next[0]['b'] = 1
next[0]['c'] = 2
...

当在位置0时，下一个a出现在位置3，下一个b在位置1，c在位置2。

3. Java代码实现

public class SubsequenceAutomaton {private int[][] next; // next[i][c]: 位置i后字符c的下一个位置public SubsequenceAutomaton(String s) {int n = s.length();int CHAR_SET_SIZE = 256; // 假设处理ASCII字符next = new int[n + 1][CHAR_SET_SIZE];Arrays.fill(next[n], -1); // 末尾位置无后续字符// 逆序填充next数组for (int i = n - 1; i >= 0; i--) {System.arraycopy(next[i + 1], 0, next[i], 0, CHAR_SET_SIZE);next[i][s.charAt(i)] = i + 1; // 记录当前字符的位置}}// 判断sub是否是s的子序列public boolean isSubsequence(String sub) {int pos = 0;for (char c : sub.toCharArray()) {pos = next[pos][c];if (pos == -1) return false;}return true;}public static void main(String[] args) {String s = "abcab";SubsequenceAutomaton automaton = new SubsequenceAutomaton(s);System.out.println(automaton.isSubsequence("ab")); // trueSystem.out.println(automaton.isSubsequence("acb")); // false（顺序不匹配）System.out.println(automaton.isSubsequence("aba")); // true}
}

4. 复杂度分析

预处理时间：O(n * |Σ|)，其中n为字符串长度，|Σ|为字符集大小（如ASCII为256）。
查询时间：O(m)，m为子序列长度。
空间复杂度：O(n * |Σ|)。

5. 优化与扩展

动态字符集支持：
- 若处理Unicode字符（如中文），需使用HashMap替代数组，但会牺牲部分性能：
```
List<Map<Character, Integer>> next = new ArrayList<>();
```
空间优化：
- 对于长字符串，可改用延迟构建或压缩状态，但会增加查询时间。
多模式匹配：
- 结合AC自动机，支持同时匹配多个子序列。