序列自动机：重复子序列问题

迈不过友情╰ 2023-10-06 19:41 1阅读 0赞

## 序列自动机：重复子序列问题 ##

#### 问题： ####

![在这里插入图片描述][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]

#### 思路： ####

我们可以用序列自动机来判断子序列，如何处理A可重复的问题呢？我们并不需要真的重复A，当我们用序列自动机判断某个元素不存在时，A重复后该元素可能会出现（即该元素在遍历位置之前），因此我们重新回到位置1开始继续找寻该元素即可，同时重复次数+1  
  如何判断无论重复多少次都不可能为子序列？若A无论重复多少次，B都不会是A的子序列，则表明B中含有A中没有的字符（若B中的字符A中都有，则进行多次重复后，一定能在A中找到B中对应的字符）。那么如何判断B中是否含有A中没有的字符呢？我们不需使用set保存出现的字符，利用序列自动机，若在位置1调用Next\[1\]\[\]都找不到该字符的时候，就说明整个A串都不包含该字符，返回-1即可

#### 代码： ####

import java.util.*;
    
    public class Main {
        
        static int[][] next = new int[100002][26];
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            String A, B;
            int i, j;
            while (scanner.hasNext()) {
        
                A = scanner.next();
                B = scanner.next();
                Arrays.fill(next[A.length() + 1], 0);
                for (i = A.length();i >= 1;i--) {
        
                    for (j = 0;j < 26;j++) {
        
                        next[i][j] = next[i + 1][j];
                    }
                    next[i][A.charAt(i - 1) - 'a'] = i;
                }
                System.out.println(check(B));
            }
    
        }
    
        static int check(String B) {
        
            int i, ans = 1, pos = 1, temp;
            for (i = 0;i < B.length();i++) {
        
                temp = next[pos][B.charAt(i) - 'a'];
                if (temp == 0) {
        
                    if (pos == 1) {
        
                        return -1;
                    }
                    ans++;
                    i--;
                    pos = 1;
                } else {
        
                    pos = temp + 1;
                }
            }
            return ans;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/ea7e0b8c3d4a41768ba93cebd555d0a5.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/8c5e57ee8aa545b6a87eee38744b7efc.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16