典题

求给定一个字符串$S$，计算$S$的不同非空子序列的个数

顺序考虑每个字符作为子序列结尾的贡献

为了避免重复, 每次只考虑倒数第二个字符最后一次出现的贡献(因为之前的子序列【最后一个字符相同】都是最后一次出现的真子集)

vector<int> f(26, 0);
int res = 0; // res是目前所有子序列(以结尾字符不同划分)
for (int i = 0; i < n; i ++)
{
    int tmp = f[s[i] - 'a'];
    f[s[i] - 'a'] = (res + 1) % mod; // 考虑当前字符串的贡献
    // 更新以s[i] - 'a'为结尾的子序列的贡献
    res = (res - tmp + mod) % mod;
    res = (res + f[s[i] - 'a']) % mod;
}

给定字符串$S$和$T$，判断$S$是否为$T$的子序列

$f[i][j]$表示字母$j$在从下标$i$开始第一次出现的位置

bool isSubsequence(string s, string t)
{
    int n = s.size(), m = t.size();

    vector<vector<int>> f(m + 1, vector<int>(26, 0));
    for (int i = 0; i < 26; i++) f[m][i] = m;

    for (int i = m - 1; i >= 0; i--)
    {
        for (int j = 0; j < 26; j++)
        {
            if (t[i] == j + 'a')
                f[i][j] = i;
            else
                f[i][j] = f[i + 1][j];
        }
    }
    int add = 0;
    for (int i = 0; i < n; i++)
    {
        if (f[add][s[i] - 'a'] == m)
        {
            return false;
        }
        add = f[add][s[i] - 'a'] + 1;
    }
    return true;
}

例题

Strings, Subsequences, Reversed Subsequences, Prefixes

考虑两种情况:

1. 前后缀不交叉, 那方案数就为中间字符串子序列的个数(注意要算空串)

2. 前后缀交叉: 先求出前后顺序在原串中出现的下标, 再考虑T串的后缀回文序列, 判断以当前回文序列为公共部分是否可以从原串取到