algo-aha

“不同”子序列，按照字母做某种划分

串的不同子序列数

• https://leetcode.com/problems/distinct-subsequences-ii/

int distinctSubseqII(string S) {
    const int MOD = 1e9 + 7;
    vector<int> endsWith(26, 0); // 扫描到S[i]时、以各字母结尾的子序列数
    for (char c : S) {
        // 原先子序列都扩展个c，有sum(endsWith[])个；还有1个新的字母c序列
        // (不用担心旧的字母c序列，它被扩展成cc序列，和新的字母c序列不冲突)
        endsWith[c - 'a'] = accumulate(begin(endsWith), end(endsWith), 1L) % MOD;
    }
    return accumulate(begin(endsWith), end(endsWith), 0L) % MOD;
}

循环字母串中，串的不同子串数

• https://leetcode.com/problems/unique-substrings-in-wraparound-string/

int findSubstringInWraproundString(string p) {
    // 找以各个字母结尾的最长子串长
    // 比如以d结尾的最长子串bcd长3，它就贡献了d、cd、bcd三个子串
    vector<int> endsWith(26);
    int len = 0;
    for (int i = 0; i < p.size(); i++) {
        if (i > 0 && (p[i] == p[i-1] + 1 || p[i] == p[i-1] - 25)) len++;
        else len = 1;
        int charIdx = p[i] - 'a';
        endsWith[charIdx] = max(endsWith[charIdx], len);
    }

    return accumulate(begin(endsWith), end(endsWith), 0);
}

短串列表中，长串的子序列数

• https://leetcode.com/problems/number-of-matching-subsequences/

可一个个判断。也可将短串按待匹配字母分桶。

int numMatchingSubseq(string S, vector<string>& words) {
    // 将word按待匹配char分桶，charToMatch=>{wordIdx,charIdxInWord}
    vector<pair<int, int>> buckets[128];
    for (int i = 0; i < words.size(); i++) {
        buckets[words[i][0]].push_back({i, 0});
    }
    
    for (char c : S) { // 待匹配字母c
        auto cBucket = buckets[c];
        buckets[c].clear();
        for (auto [wordIdx, charIdx] : cBucket) { // 桶中word都匹配掉c
            charIdx++;
            buckets[words[wordIdx][charIdx]].push_back({wordIdx, charIdx});
        }
    }
    // 全单词匹配的最后分到'\0'桶里
    return buckets[0].size();
}

是不是长串的子序列（长串不变，有很多短串要判断）

• https://leetcode.com/problems/is-subsequence/

bool isSubsequence(string s, string t) {
    // follow up，预处理长串t，记录各字母出现的位置列表
    vector<vector<int>> pos(26);
    for (int i = 0; i < t.size(); i++) {
        pos[t[i] - 'a'].push_back(i);
    }

    int lastIdx = -1;
    for (char c : s) { // 应在各字母的位置列表穿梭前进
        auto &list = pos[c - 'a'];
        auto it = upper_bound(list.begin(), list.end(), lastIdx);
        if (it == list.end()) return false;
        lastIdx = *it;
    }
    return true;
}