C++で文字列の検索と置換を実装する方法

問題の概要

文字列 S が与えられたとき、複数の置換操作を実行して、特定の文字グループを新しい文字列に置き換えることを考えます。各置換操作には3つのパラメータがあります。開始インデックス i、検索対象の単語 x、置換後の単語 y です。

ルールは次のとおりです。もし x が元の文字列 S の位置 i から始まっている場合は、その出現箇所を y に置き換えます。そうでない場合は、何も行いません。

例1

S = "abcd" という文字列に対し、置換操作 i = 2、x = "cd"、y = "ffff" を適用するとします。「cd」は元の文字列 S の位置2から始まっているため、この部分を「ffff」に置き換えます。

例2

同じく S = "abcd" に対し、置換操作 i = 0、x = "ab"、y = "eee" と、もう一つの操作 i = 2、x = "ec"、y = "ffff" の両方を適用する場合を考えます。このとき2番目の操作は何も行いません。なぜなら、元の文字列では S[2] = 'c' であり、x[0] = 'e' と一致しないからです。

例3

S = "abcd"、indexes = [0, 2]、sources = ["a", "cd"]、targets = ["eee", "ffff"] が与えられた場合、出力は「eeebffff」となります。これは「a」が S の位置0から始まるため「eee」に置き換えられ、「cd」がインデックス2から始まるため「ffff」に置き換えられるからです。

解決のアプローチ

この問題を解くには、以下の手順に従います。

• (インデックス, 元の配列内の位置) のペアを格納する配列 sorted を定義します。n は indexes 配列のサイズです。
• i を 0 から n-1 まで繰り返し、ペア (indexes[i], i) を sorted に挿入します。
• sorted を降順(大きいインデックス順)にソートします。
• j を 0 から n-1 まで繰り返します。
  • i := sorted[j] の1番目の値
  • src := sources[sorted[j] の2番目の値]
  • target := targets[sorted[j] の2番目の値]
  • S のインデックス i から始まる長さ src.size() の部分文字列が src と一致する場合:
    • S := (S の先頭から i までの部分文字列) + target + (S の i + source.size() 以降の部分文字列)
• 最後に S を返します。

降順にソートする理由は、後ろのインデックスから処理することで、置換によって文字列の長さが変わっても、まだ処理していない前の方のインデックス位置がずれないようにするためです。

C++での実装例

以下の実装を見ると、理解がより深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string findReplaceString(string S, vector<int>& indexes, vector<string>& sources, vector<string>& targets) {
      vector < pair <int, int> > sorted;
      int n = indexes.size();
      for(int i = 0; i < n; i++){
         sorted.push_back({indexes[i], i});
      }
      sort(sorted.rbegin(), sorted.rend());
      for(int j = 0; j < n; j++){
         int i = sorted[j].first;
         string source = sources[sorted[j].second];
         string target = targets[sorted[j].second];
         if(S.substr(i, source.size()) == source){
            S = S.substr(0, i) + target + S.substr(i + source.size());
         }
      }
      return S;
  }
};
main(){
   vector<int> v1 = {0, 2};
   vector<string> v2 = {"a", "cd"};
   vector<string> v3 = {"eee", "ffff"};
   Solution ob;
   cout << (ob.findReplaceString("abcd", v1, v2, v3));
}

入力

"abcd"
[0, 2]
["a", "cd"]
["eee", "ffff"]

出力

eeebffff

まとめ

このアルゴリズムでは、まずすべての置換操作を開始インデックスの降順に並べ替えてから処理を行います。これにより、文字列の置換による長さの変化が他の操作のインデックスに影響を与えることを防げます。計算量は、ソートに O(n log n)、各置換操作で部分文字列の比較と連結が必要なため、全体として効率的に動作します。substr() を使った部分文字列の一致判定と連結というシンプルな手法で、指定位置における条件付き文字列置換を確実に実現できます。