C++で文字列内の最初に繰り返される単語を検索する方法

この問題では、スペースで区切られた複数の単語からなる文字列 str が与えられます。私たちのタスクは、文字列の中で最初に繰り返し出現する単語を見つけることです。

つまり、「2つのスペースに挟まれた単語」の中から、文字列内で重複して現れる最初のものを特定する必要があります。

問題を理解するための例

入力 : str = "C program are easy to program"
出力 : program

解決アプローチ

この問題に対するシンプルな解決策は、ハッシュマップ（unordered_map）というデータ構造を利用することです。

まず、文字列を単語ごとに分割しながら読み込み、各単語とその出現回数をハッシュマップに記録していきます。このとき、現在処理している単語がすでにマップに登録されているかどうかを確認し、存在すればカウントを1つ増やし、存在しなければ新規に登録します。

すべての単語を記録した後、再び文字列を先頭から走査し、ハッシュマップ上で出現回数が2以上となっている最初の単語を答えとして返します。

アルゴリズムの手順

1. istringstream を使って文字列を単語単位に分割する
2. 各単語の出現回数を unordered_map に記録する
3. 再度文字列を先頭から走査し、出現回数が2以上の最初の単語を返す
4. 該当する単語が存在しない場合は「NoRepetition」を返す

実装例

以下は、この解決策の動作を示すC++プログラムです。

#include <bits/stdc++.h>
using namespace std;
string findFirstRepeatWord(string str){
    istringstream iss(str);
    string word;
    unordered_map<string, int> wordCountMap;
    while (getline(iss, word, ' ')) {
        if (wordCountMap.find(word) != wordCountMap.end())
            wordCountMap[word] ++;
        else
            wordCountMap.insert(make_pair(word, 1));
    }
    istringstream iss2(str);
    while (getline(iss2, word, ' ')) {
        int count = wordCountMap[word];
        if (count > 1) {
            return word;
        }
    }
    return "NoRepetition";
}
int main(){
    string str = "C program are easy to program";
    string repeatedWord = findFirstRepeatWord(str);
    if (repeatedWord != "NoRepetition")
       cout<<"The first repeated word is '"<<repeatedWord<<"'";
    else
      cout<<"No word is Repeated in the string";
   return 0;
}

出力結果

The first repeated word is 'program'

コードの解説

このプログラムでは、タスクを簡潔に実装するために標準ライブラリの便利な機能をいくつか活用しています。

• istringstream：文字列をストリームとして扱い、単語ごとに分割して読み込むことができます。
• getline()：第3引数に区切り文字（ここではスペース）を指定することで、単語単位で抽出できます。
• unordered_map：キー（単語）と値（出現回数）のペアを管理し、平均 O(1) の時間計算量で検索・挿入が可能です。

このアルゴリズム全体の時間計算量は O(n)、空間計算量も O(n) となります（n は文字列の長さ）。文字列を2回走査するためシンプルで分かりやすい実装であり、大量のテキストデータにも効率的に対応できます。