子序列自动机

子序列自动机

根本概念

子序列自动机 是一种高效处理惩罚 子序列匹配 题目的数据结构。

焦点头脑： 预处理惩罚出从每个位置 \(i\) 开始(包罗 \(i\) )，每个字符 \(c\) 下一次出现的位置。
界说：

• n: 字符串 \(s\) 的长度。
  
• \(\sum\) : 字符集巨细。
  
• nxt[c]: 体现从位置 \(i ~ (0 \le i \le n)\) 开始，字符 \(c\) 第一次出现的位置。若不存在，则设为 \(n\) (大概 \(n + 1\) )。
  

构建方法

二维数组法(小字符集)

1. string s; cin >> s;
2. int n = s.size();
3. vector<vector<int> > nxt(n + 1, vector<int> (26, n));
4. for(int i = n - 1; i >= 0; i --){
5.     nxt[i] = nxt[i + 1];
6.     nxt[i][s[i] - 'a'] = i;
7. }

复制代码

时间复杂度: \(O(n \cdot \sum)\)
二分查找法(大字符集)

1. vector<int> pos[N]; // N: 字符集大小
2. for(int i = 0; i < n; i ++){
3.     pos[arr[i]].emplace_back(i);
4. }
5. // 查询字符 c 在位置 cur 之后的下一个位置
6. auto it = upper_bound(pos[c].begin(), pos[c].end(), cur);
7. if(it == pos[c].end()){
8.     // 不存在
9. }else{
10.     // 下一个位置 = *it;
11. }

复制代码

时间复杂度: 构建 \(O(n)\)，单次查询 \(O(log~n)\)
重要应用

判定是否为子序列

给出模式串 \(T\)，判定是否为 \(S\) 的子序列。

这个给出针对 小字符集 的判定方法。

1. int cur = 0;
2. for(char ch : T){
3.     cur = nxt[cur][ch - 'a'];
4.     if(cur == n) return false;
5. }
6. return true;

复制代码

盘算差异的子序列

差异的子序列 II : 给定一个字符串 \(s\)，盘算 \(s\) 的 差异非空子序列 的个数(答案对 1e9 + 7 取余)。

子序列自动机+DP

界说:

• dp: 从下标 \(i\) 开始到字符串末端，可以大概构成的 全部差异子序列的数目 (包罗空串)。
  

状态转移方程:

\[dp = 1 + \sum_{c = 0}^{25} dp\left[nxt[c] + 1\right]\]

• 1: 体现当前位置留空。
  
• \(\sum_{c = 0}^{25} dp\left[nxt[c] + 1\right]\): 罗列当前位置须要放置的每个字符 \(c\) 。
  
  
  
  • nxt[c]: 体现从 \(i\) 位置开始下一个字符 \(c\) 的位置。
    
  • nxt[c] + 1: 确定字符 \(c\) 后，字符 \(c\) 的下一个位置。
    
  • dp[nxt[c] + 1]: 字符 \(c\) 背面可以跟的差异子序列的数目。
    
  
  

代码:

1. class Solution {
2. public:
3.     int distinctSubseqII(string s) {
4.         int n = s.size();
5.         int mod = 1e9 + 7;
6.         // 初始化 子序列自动机
7.         vector<vector<int> > nxt(n + 1, vector<int> (26, n));
8.         for(int i = n - 1; i >= 0; i --){
9.             nxt[i] = nxt[i + 1];
10.             nxt[i][s[i] - 'a'] = i;
11.         }
12.         // dp[i] := 从下标 i 开始到字符串末尾，能够组成的 所有不同子序列 的数量(包括空串)
13.         vector<int> dp(n + 1, 0);
14.         dp[n] = 1; // 空串的不同子序列数量也为 1
15.         for(int i = n - 1; i >= 0; i --){
16.             dp[i] ++; // 当前位置字符为空
17.             for(int c = 0; c < 26; c ++){
18.                 if(nxt[i][c] != n){ // 避免 i 位置及以后不存在字符 c
19.                     dp[i] = ((long long)dp[i] + dp[nxt[i][c] + 1]) % mod;
20.                 }
21.             }
22.         }
23.         return (dp[0] - 1 + mod) % mod; // 排除 dp[0] - 1 取负
24.     }
25. };

复制代码

时间复杂度: \(O(n \cdot \sum)\)
线性DP

这里更加保举利用 线性DP 来办理这题。

界说:

• last[c]: 字符 c 末了出现的位置。
  
• dp: \(s[0, i]\) 子串中差异子序列的数目。
  

状态转移方程:

\[dp = (dp[i - 1] \times 2 - dp[last[c] - 1] + MOD) ~ \% ~ MOD\]

• dp[i - 1] * 2: \(i\) 位置有 选 和 不选 两种状态。
  
• - dp[last[c] - 1]: 之前出现过字符 \(c\) ，会重复思量 \(s\left[0,~ last[c] - 1\right]\) 部门的 差异子序列个数。
  

代码:

1. class Solution {
2. public:
3.     int distinctSubseqII(string s) {
4.         int n = s.size();
5.         int mod = 1e9 + 7;
6.         s = " " + s; // 统一起始索引从 1 开始
7.         unordered_map<char, int> last; // last[c]:= 字符 c 最后出现的位置
8.         // dp[i] := s[0, i]子串中不同子序列的数量
9.         vector<int> dp(n + 1, 0);
10.         dp[0] = 1; // 空串的不同子序列数量为 1
11.         for(int i = 1; i <= n; i ++){
12.             dp[i] = dp[i - 1] * 2 % mod;
13.             if(last.count(s[i])){ // 减去重复部分
14.                 dp[i] = (dp[i] - dp[last[s[i]] - 1] + mod) % mod;
15.             }
16.             last[s[i]] = i; // 更新字符最后出现的位置
17.         }
18.         return (dp[n] - 1 + mod) % mod;
19.     }
20. };

复制代码

时间复杂度: \(O(n \cdot \sum)\)