C++で文字列の一意な部分列の個数を数えるプログラム

文字列 s が与えられたとき、s の空でない一意な部分列(サブシーケンス)の個数を求めることを考えます。答えが非常に大きくなる可能性があるため、結果は 10⁹ + 7 で割った余りを返します。

例えば、入力が s = "xxy" の場合、出力は 5 になります。「x」「xx」「xy」「y」「xxy」の5つの異なる部分列が存在するためです。

解法のアプローチ

この問題は、各文字について「その文字で終わる新しい部分列の数」を逐次計算していくことで解けます。手順は以下の通りです。

• m := 10⁹ + 7(剰余を取るための定数)
• n := 文字列 s の長さ
• サイズ26の配列 table を定義(各アルファベットごとの部分列数を記録)
• res := 0(これまでに見つかった一意な部分列の総数)
• i := 1 から n まで、i を1ずつ増やしながら以下を繰り返す:
  • c := s[i − 1] − 'a'(現在の文字のインデックス)
  • curr := (res + 1 − table[c] + m) mod m(この文字で新たに作られる部分列の数)
  • res := (res + curr) mod m
  • table[c] := (table[c] + curr) mod m
• res を返す

アルゴリズムのポイント

このアルゴリズムの鍵となるのは、配列 table の使い方です。table[c] には「文字 c で終わる部分列の累積数」が記録されており、同じ文字が再び現れたときに、以前にカウント済みの部分列を差し引くことで重複を効率的に排除できます。これにより、全体的な計算量は O(n) に抑えられ、非常に大きな文字列でも高速に処理可能です。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
int solve(string s) {
    int n = s.size();
    vector<int> table(26);
    long long res = 0;
    for (int i = 1; i <= n; ++i) {
        int c = s[i − 1] − 'a';
        int curr = (res + 1 − table[c] + m) % m;
        res = (res + curr) % m;
        table[c] = (table[c] + curr) % m;
    }
    return res;
}
int main(){
    string s = "xxy";
    cout << solve(s);
}

入力

"xxy"

出力

5