序列自动机：判断子序列

我就是我 2023-10-06 19:40 40阅读 0赞

## 序列自动机：判断子序列 ##

#### 文章目录 ####

*  序列自动机：判断子序列
 *   *   *  序列自动机
         *  问题：
         *  思路：
         *  代码：

#### 序列自动机 ####

设想这样一个问题：判断字符串 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出现的第一个位置)。结合图例来理解：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]  
  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。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
  从下标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

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

#### 问题： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][f05ecd57a6d84407bdebbd7332b97690.png]  
  使用序列自动机，解决的是上图中的进阶问题

#### 思路： ####

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

#### 代码： ####

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;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/3c7ab9bda323456ba57da959a4944d16.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/eb9005b7c7de429fb72e6f248f1bcbc5.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/598e32839b8b4faa9a2f3b3048fb9cdc.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[f05ecd57a6d84407bdebbd7332b97690.png]: https://img-blog.csdnimg.cn/f05ecd57a6d84407bdebbd7332b97690.png