序列自动机：判断子序列

文章目录

序列自动机：判断子序列

序列自动机

设想这样一个问题：判断字符串 s 是否为字符串 t 的子序列（注意子序列和子串不同，子串要求连续，子序列不要求连续），我们可以使用双指针，两个指针分别从s和t的第一个元素开始，不断进行匹配移动，时间复杂度为O(n+m)，n,m分别为s和t的长度。但若有大量输入的 S，称作 S1, S2, … , Sk 其中k非常大，例如k >= 10亿，你需要依次检查它们是否为 T 的子序列，若我们仍然使用双指针进行逐个判断，时间复杂度为O(k * m + ∑n)，这样的时间复杂度是我们无法接受的，这时序列自动机就该登场了，序列自动机使用空间换时间的思想，能将上述时间复杂度优化到O(m + ∑n)，把非常大的参数k消去了。
序列自动机是一个可以快速判断字符串s是否是字符串t的子序列的一个方法（在存在非常多的s需要判断的情况下）。
序列自动机使用了一个二维数组next[i] [j]，next[i] [j]表示从第i个位置起，字符j出现的第一个位置。
以判断子序列为例（设序列全由小写字母组成），我们可以创建一个二维数组Next[N][26]，第一维的N指序列长度，第二维指26个字母。那么Next[a][b]里面存的是什么信息呢？存的是从字符串的第a位开始距离第a
位最近的字符b的下标(即从第a个位置起，字符b出现的第一个位置)。结合图例来理解：

Next[1] [3]表示从第1个位置起，字符d出现的第一个位置（3就是表示d，26个字母表示为数字0 ~ 25），在上图中Next[1] [3] = 4。Next[5] [1]同理，表示从第5个位置起，字符b出现的第一个位置（距离第5位最近的字符b的下标），为7。

我们如何使用上述Next数组判断字符串s是否为t的子序列呢？举个例子，设t=acbdacbad，s=abcd，那么求s是否为t的子序列可以拆分为4个小问题：
(1)t串中距离下标1最近的’a’在哪？答：Next[1][0]=1。
(2)t串中距离下标Next[1][0]+1=2最近的’b’在哪？答：Next[2][1]=3。
(3)t串中距离下标Next[2][1]+1=4最近的’c’在哪？答：Next[4][2]=6。
(4)t串中距离下标Next[4][2]+1=7最近的’d’在哪？答：Next[7][3]=9。

从下标1开始，我们利用Next数组逐个查询s中每个字符出现的位置，每查到一个字符的位置，我们将该位置的下一位作为新起点，继续利用Next数组查询，若s中每个字符的位置都能查到，则s为子序列，否则不是子序列。
设Next[i] [j] = 0表示从位置i开始，字符j不存在，则利用Next数组判断s是否为子序列的算法模板如下：

    static boolean check(String s) {
        int i, pos = 1;
        for (i = 0;i < s.length();i++) {
            pos = next[pos][s.charAt(i) - 'a'];
            if (pos == 0) {
                return false;
            }
            pos++;
        }
        return true;
    }

解决了利用Next数组判断子序列的问题，接下来我们要解决Next数组的创建问题。
注意到Next数组保存的是后方距离最近的字符的位置信息，既然是后面的信息，那么我们从后往前扫一遍，前一位完全可以继承后一位的信息。例如，Next[i + 1][j]表示从i + 1位开始，字符j第一次出现的位置，那么如果第i位的元素不为字符j，那么Next[i][j] = Next[i + 1][j]，因为第i位不为字符j，从第i位开始看和从i + 1位开始看，字符j第一次出现的位置是一样的。因此我们可以从后往前扫描，创建Next数组，若当前遍历到第i位，Next[i][]可以先完全继承Next[i + 1][]的信息，接着将第i位的字符信息覆盖更新即可，即Next[ i ][ t[ i ] ] = i。设用0表示不存在，创建Next数组的算法模板如下：

		int[][] next = new int[t.length() + 2][26];
        for (i = t.length();i >= 1;i--) {
            for (j = 0;j < 26;j++) {
                next[i][j] = next[i + 1][j];
            }
            next[i][t.charAt(i - 1) - 'a'] = i;
        }

这里注意定义int数组后，其默认值就是0

综上即是利用序列自动机判断子序列的流程。

问题：

使用序列自动机，解决的是上图中的进阶问题

思路：

使用序列自动机判断子序列

代码：

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i, j;
        int[][] next = new int[t.length() + 2][26];
        for (i = t.length();i >= 1;i--) {
            for (j = 0;j < 26;j++) {
                next[i][j] = next[i + 1][j];
            }
            next[i][t.charAt(i - 1) - 'a'] = i;
        }
        if (check(s, next)) {
            return true;
        } else {
            return false;
        }
    }

    static boolean check(String s, int[][] next) {
        int i, pos = 1;
        for (i = 0;i < s.length();i++) {
            pos = next[pos][s.charAt(i) - 'a'];
            if (pos == 0) {
                return false;
            }
            pos++;
        }
        return true;
    }
}