简介

自动机是一种通过状态之间的跳转进行计算的数学模型。

当自动机接受一个输入字符时，它使用状态转移函数，依据当前所处的状态和输入的字符跳转至下一个状态。我们常常使用有向图表示一个有限状态自动机。此时，状态在有向图上以结点形式表示；状态转移函数表示为这张图上的有向边的集合。

比如说判断一个二进制串的奇偶性，我们可以建出以下这个自动机：

这个自动机初始状态为 \(q_0\)，如果最终状态为 \(q_0\)，则该二进制串为偶数，否则为奇数。

子序列自动机

首先考虑怎么判断一个字符串 \(T\) 是否是字符串 \(S\) 的子序列。

可以用类似于贪心的方法：令 \(q_i\) 表示当前字符串匹配到了 \(S\) 的第 \(i\) 个字符。\(q_{0}\) 为初始状态。\(q_{-1}\) 表示当前字符串不是 \(S\) 的子序列。而转移 \(\delta(q_i,c)\) 就为 \(i\) 之后第一次字符 \(c\) 的出现位置。若没有，则为 \(-1\)。

例如 \(S=abaab\) 时自动机如下：

这时我们可以发现，所有在这个自动机上以 \(q_0\) 为起点，不以 \(q_{-1}\) 为终点的路径都对应着一个子序列，并且这些子序列都是本质不同的。

原因很简单：因为自动机中是取最近的一个字符，所以就不会有重复。

然后在这个自动机上做 \(dp\) 即可求出 \(S\) 的本质不同子序列数量。

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 100005, MOD = int(1e9) + 7;

int t, n, dp[MAXN], ans, r[MAXN][26];
string s;

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> s;
  n = s.size(), s = ' ' + s;
  fill(&r[n + 1][0], &r[n + 1][26], n + 1);
  for(int i = n; i >= 0; --i) {
    dp[i] = 0;
    for(int j = 0; j < 26; ++j) {
      r[i][j] = r[i + 1][j];
    }
    if(i < n) {
      r[i][s[i + 1] - 'A'] = i + 1;
    }
  }
  dp[0] = 1, ans = 0;
  for(int i = 0; i <= n; ++i) {
    for(int j = 0; j < 26; ++j) {
      dp[r[i][j]] = (dp[r[i][j]] + dp[i]) % MOD;
    }
    ans = (ans + dp[i]) % MOD;
  }
  cout << ans << "\n";
  return 0;
}