Count Substrings
(lib/dp/substring.hpp)

• View this file on GitHub
• Last update: 2024-05-04 18:06:16+09:00
• Include: #include "lib/dp/substring.hpp"

Count Substrings

概要

配列における、連続するとは限らない部分列の種類数を数え上げます。

使い方

• substrings(s, m): 文字列 $s$ における、連続しない部分文字列の種類数を $m$ で割った余りを返します。(空文字列を含む)
• subsequences(s, m): 列 $s$ における、連続するとは限らない部分列の種類数を $m$ で割った余りを返します。

計算量

配列の要素数を $N$ とする。

• substrings(s, m): $\mathrm{O}(N)$
• subsequences(s, m): $\mathrm{O}(N \log N)$

Verified with

• test/library_checker/enumerative_combinatorics/number_of_subsequences.test.cpp

Code

#pragma once

/**
 * @brief Count Substrings
 * @docs docs/dp/substring.md
 */

long long substrings(const string &s, const long long &m){
    int n = (int) s.size();

    vector<vector<int>> next(n + 1, vector<int>(26, n));
    for(int i = n - 1; i >= 0; i--){
        next[i] = next[i + 1];
        next[i][s[i] - 'a'] = i;
    }

    vector<long long> dp(n + 1, 0);
    dp[0] = 1;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < 26; ++j){
            if(next[i][j] >= n) continue;
            dp[next[i][j] + 1] += dp[i];
            dp[next[i][j] + 1] %= m;
        }
    }

    long long res = 0;
    for(int i = 0; i <= n; ++i){
        res += dp[i]; res %= m;
    }
    return res;
}

template <typename T>
long long subsequences(const vector<T> &s, const long long &m){
    int n = (int) s.size();
    map<T, int> mp;
    vector<long long> dp(n + 1);
    dp[0] = 1;
    for(int i = 0; i < n; i++){
        if(mp.count(s[i]) != 0){
            dp[i + 1] = dp[i] * 2 + m - dp[mp[s[i]]];
        } else{
            dp[i + 1] = dp[i] * 2;
        }
        dp[i + 1] %= m;
        mp[s[i]] = i;
    }
    return dp[n];
}

#line 2 "lib/dp/substring.hpp"

/**
 * @brief Count Substrings
 * @docs docs/dp/substring.md
 */

long long substrings(const string &s, const long long &m){
    int n = (int) s.size();

    vector<vector<int>> next(n + 1, vector<int>(26, n));
    for(int i = n - 1; i >= 0; i--){
        next[i] = next[i + 1];
        next[i][s[i] - 'a'] = i;
    }

    vector<long long> dp(n + 1, 0);
    dp[0] = 1;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < 26; ++j){
            if(next[i][j] >= n) continue;
            dp[next[i][j] + 1] += dp[i];
            dp[next[i][j] + 1] %= m;
        }
    }

    long long res = 0;
    for(int i = 0; i <= n; ++i){
        res += dp[i]; res %= m;
    }
    return res;
}

template <typename T>
long long subsequences(const vector<T> &s, const long long &m){
    int n = (int) s.size();
    map<T, int> mp;
    vector<long long> dp(n + 1);
    dp[0] = 1;
    for(int i = 0; i < n; i++){
        if(mp.count(s[i]) != 0){
            dp[i + 1] = dp[i] * 2 + m - dp[mp[s[i]]];
        } else{
            dp[i + 1] = dp[i] * 2;
        }
        dp[i + 1] %= m;
        mp[s[i]] = i;
    }
    return dp[n];
}

Back to top page