【C++】文字列内に現れる部分文字列のすべての出現位置（インデックス）を検索する方法

問題の概要

文字列 str と、その中から探したい部分文字列 sub_str が与えられたとき、sub_str が str 内に出現するすべての位置（インデックス）を求めることを考えます。

例えば、str が「aabbababaabbbabbaaabba」、sub_str が「abb」である場合、出現位置は 1 9 13 18 となります。

解決のアプローチ：substr() 関数の活用

この問題は、C++ STL に用意されている substr() 関数を使うことで簡単に解決できます。substr() 関数は、第1引数に検索を開始する位置、第2引数に切り出す文字列の長さを指定すると、その範囲の部分文字列を返します。ループで各位置から部分文字列を切り出し、それが sub_str と一致するかどうかを順番に比較していけば、すべての出現位置を発見できます。

サンプルコード

#include<iostream>
using namespace std;
void substrPosition(string str, string sub_str) {
   bool flag = false;
   for (int i = 0; i < str.length(); i++) {
      if (str.substr(i, sub_str.length()) == sub_str) {
         cout << i << " ";
         flag = true;
      }
   }
   if (flag == false)
      cout << "NONE";
}
int main() {
   string str = "aabbababaabbbabbaaabba";
   string sub_str = "abb";
   cout << "Substrings are present at: ";
   substrPosition(str, sub_str);
}

実行結果

Substrings are present at: 1 9 13 18

コードのポイント

・文字列 str の先頭から末尾まで、位置 i を1文字ずつずらしながら走査します。
・各位置 i において、str.substr(i, sub_str.length()) で sub_str と同じ長さの部分文字列を取り出し、sub_str と比較します。
・一致した場合はそのインデックス i を出力し、フラグ flag を true に設定します。
・最後まで一度も一致しなかった場合（flag が false のままの場合）は「NONE」を出力し、部分文字列が存在しないことを示します。

計算量について

文字列 str の長さを n、部分文字列 sub_str の長さを m とすると、この方法の計算量は O(n × m) になります。単純な手法ですが、ロジックが分かりやすく、小〜中規模の文字列であれば十分実用的です。より大きなデータを扱う場合は、string::find() をループで利用する方法や、KMP法などの効率的な文字列照合アルゴリズムを検討するとよいでしょう。