C++ STLを使った長さ2の異なる連続部分文字列の個数を数える方法

はじめに

本記事では、C++のSTL(標準テンプレートライブラリ)を活用して、与えられた文字列の中に現れる長さ2の異なる連続部分文字列を抽出し、それぞれの出現回数を数えて表示するプログラムについて解説します。

問題の概要

入力として1つの文字列が与えられます。私たちのタスクは、文字列から隣接する2文字ずつを取り出し、重複を除いたすべての部分文字列(長さ2)とその出現回数を求めて出力することです。

例えば、文字列 "abcacdcacabacaassddssklac" の場合、「ab」「bc」「ca」などのペアが登場します。同じペアが何度現れても1種類として扱い、出現回数を記録するのがポイントです。

実装のアプローチ

この問題は、std::map と std::pair を組み合わせることで簡潔に解決できます。

• キー: 隣接する2文字 (str[i], str[i+1]) を pair<char, char> として表現
• 値: そのペアが出現した回数(int)

map は自動的にキーでソートされるため、結果は昇順に整列されて出力されます。

サンプルコード

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

void calc_distinct(string str){
    // 2文字のペアごとの出現回数を記録するマップ
    map<pair<char,char>, int> dPairs;

    for (int i=0; i<str.size()-1; i++)
        dPairs[make_pair(str[i], str[i+1])]++;

    cout << "Distinct sub-strings with counts:\n";
    for (auto it=dPairs.begin(); it!=dPairs.end(); it++)
        cout << it->first.first << it->first.second << "-" << it->second << " ";
}

int main(){
    string str = "abcacdcacabacaassddssklac";
    calc_distinct(str);
    return 0;
}

実行結果

Distinct sub-strings with counts:
aa-1 ab-2 ac-4 as-1 ba-1 bc-1 ca-4 cd-1 dc-1 dd-1 ds-1 kl-1 la-1 sd-1 sk-1 ss-2

コードの解説

1. マップの準備: dPairs は、2文字のペアをキー、出現回数を値として保持します。
2. 走査とカウント: ループで文字列を先頭から末尾まで走査し、各位置で現在の文字と次の文字をペアにして、マップ内の該当キーのカウントをインクリメントします。
3. 結果の出力: イテレータでマップを巡回し、「2文字のペア - 出現回数」の形式で出力します。map の特性により、キーは昇順に並んでいます。

まとめ

C++ STLの map を使えば、長さ2の異なる連続部分文字列の抽出と出現回数の集計を、わずか十数行のコードで実現できます。文字列の長さをNとすると計算量は O(N log N) 程度に収まり、効率的な処理が可能です。この手法は、n-gram解析など他の文字列処理タスクにも応用できるため、ぜひ覚えておきましょう。