C++で別の文字列から構築できる文字列の出現回数を数える方法

問題概要

2つの文字列 str_1 と str_2 が入力として与えられます。求めるのは、str_1 に含まれる文字をそれぞれ1回だけ使用して、str_2 と同一の文字列を何個構築できるかという個数です。

注意： 両方の文字列に含まれるアルファベットは、すべて大文字・小文字が統一されているものとします。

具体例で確認してみましょう。

入力： str_1 = "abcaaaabca"、str_2 = "bca"

出力： 別の文字列から構築できる文字列の出現回数： 2

説明： str_1 内には "bca" が次の2箇所に存在します。

str_1[1-3]="bca"、str_1[7-9]="bca"

入力： str_1 = "about"、str_2 = "cout"

出力： 別の文字列から構築できる文字列の出現回数： 0

説明： "cout" を構成するのに必要な文字 'c' が str_1 に存在しないため、1つも構築できません。

プログラムで使用するアプローチ

まず、str_1 に含まれるすべてのアルファベットの出現頻度を配列 arr_1[26] に、str_2 に含まれるすべてのアルファベットの出現頻度を配列 arr_2[26] に格納します。

• 2つの文字列 str_1 と str_2 を受け取り、それぞれの長さを str_1.size() および str_2.size() で取得します。
• 関数 count_string(string str_1, int len_str_1, string str_2, int len_str_2) は、両方の文字列とその長さを受け取り、str_1 から構築できる str_2 の個数を返します。
• カウント変数 count の初期値は INT_MAX とします。
• str_1 の文字出現頻度用の配列 arr_1[26] と、str_2 の文字出現頻度用の配列 arr_2[26] を0で初期化します。
• forループで str_1 と str_2 をそれぞれ走査し、arr_1 と arr_2 の頻度を更新します。
• 続いて、もう一度 forループで arr_2 を走査し、現在の頻度 arr_2[i] が0でない場合に、count(前回までの値)と arr_1[i] / arr_2[i](str_2 の各文字に対して str_1 の各アルファベットは1回しか使用しない)の小さい方を count に代入します。
• 最終的に、count には str_1 側と str_2 側の対応する文字が一致した数の最小値が入ります。たとえば aaabbbb(a=3、b=4)から abb(a=1、b=2)を作る場合、最小カウントは1になります。
• すべてのループが完了した時点での count を結果として返します。

コード例

#include <bits/stdc++.h>
using namespace std;
int count_string(string str_1, int length_str_1, string str_2, int length_str_2){
    int count = INT_MAX;
    int arr_1[26] = { 0 };
    int arr_2[26] = { 0 };
    for (int i = 0; i < length_str_1; i++){
        arr_1[str_1[i] - 'a']++;
    }
    for (int i = 0; i < length_str_2; i++){
        arr_2[str_2[i] - 'a']++;
    }
    int total_alphabets = 26;
    for (int i = 0; i < total_alphabets; i++){
        if(arr_2[i]){
            count = min(count, arr_1[i] / arr_2[i]);
        }
    }
    return count;
}
int main(){
    string str_1 = "knowledge", str_2 = "know";
    int length_str_1 = str_1.size();
    int length_str_2 = str_2.size();
    cout<<"Count occurrences of a string that can be constructed from another given string are: "<<count_string(str_1,length_str_1, str_2, length_str_2);
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

Count occurrences of a string that can be constructed from another given string are: 1

解説：なぜこの方法で求まるのか

このアルゴリズムのポイントは、「str_2 を1セット作るのに各文字がいくつ必要か(arr_2[i])」に対して、「str_1 にその文字がいくつあるか(arr_1[i])」を割り算することで、その文字だけで何セット分まかなえるかを求める点にあります。

たとえば str_1 = "knowledge"、str_2 = "know" の場合、k・n・o・w はいずれも str_1 に1回、str_2 では1回ずつ必要なので、arr_1[i] / arr_2[i] はすべて1となり、答えは1になります。仮にどれか1つの文字でも不足していれば、その文字の商が0になり、全体の結果も0となります。

計算量は、両方の文字列を1回ずつ走査するため O(N + M)(N、M はそれぞれの文字列の長さ)であり、非常に効率的です。全ての部分文字列を総当たりで調べる方法(O(N × M))と比べて、文字列が長くなっても高速に動作するのが大きな利点です。