ค้นหาและแทนที่ในสตริงใน C ++

สมมติว่าเรามีสตริง S เราจะดำเนินการแทนที่บางอย่างเพื่อแทนที่กลุ่มตัวอักษรด้วยกลุ่มใหม่ ในการแทนที่แต่ละครั้งจะมีพารามิเตอร์ 3 ตัว ได้แก่ ดัชนีเริ่มต้น i คำต้นทาง x และคำเป้าหมาย y กฎคือถ้า x เริ่มต้นที่ตำแหน่ง i ในสตริงเดิม S เราจะแทนที่การเกิดขึ้นของ x ด้วย y มิฉะนั้นเราจะไม่ทำอะไรเลย

ตัวอย่างเช่น ลองพิจารณาว่าถ้าเรามี S ="abcd" และเรามีการดำเนินการแทนที่ i =2, x ="cd", y ="ffff" ดังนั้นเนื่องจาก "cd" เริ่มต้นที่ตำแหน่ง 2 ในสตริงเดิม เราต้องแทนที่สิ่งนี้ด้วย "ffff"

ให้เราดูตัวอย่างอื่นใน S ="abcd" ถ้าเรามีทั้งการดำเนินการเปลี่ยน i =0, x ="ab", y ="eee" เช่นเดียวกับการดำเนินการเปลี่ยนอื่น i =2, x ="ec" , y ="ffff" การดำเนินการครั้งที่สองนี้ไม่ทำอะไรเลยเพราะในสตริงเดิม S[2] ='c' ซึ่งไม่ตรงกับ x[0] ='e'

ดังนั้นหากเรามีสตริง S ="abcd" ดัชนี =[0,2] และแหล่ง =["a", "cd"] และเป้าหมาย =["eee", "ffff"] ผลลัพธ์จะเป็น “อีเหี้ย”. เนื่องจาก "a" เริ่มต้นที่ตำแหน่ง 0 ใน S จึงถูกแทนที่ด้วย "eee" ตอนนี้ "cd" เริ่มต้นที่ดัชนี 2 ใน S จึงถูกแทนที่ด้วย "ffff"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดอาร์เรย์ของคู่ที่เรียกว่า sorted, n :=size of indexes array
• สำหรับ i ในช่วง 0 ถึง n – 1
  • ใส่คู่ (indexes[i], i) ลงใน sorted
• เรียงลำดับการเรียงลำดับย้อนกลับ
• สำหรับ j ในช่วง 0 ถึง n – 1
  • i :=ค่าแรกของคู่ที่เรียงลำดับ[j]
  • src :=source[ค่าที่สองของคู่ที่ sorted[j]]
  • target :=targets[ค่าที่สองของคู่ที่ sorted[j]]
  • ถ้าสตริงย่อยของ S จากดัชนี i ถึงขนาดของแหล่งที่มา – 1 เหมือนกับซอร์สแล้ว
    • S :=(สตริงย่อยของ S จากดัชนี 0 ถึง i) เชื่อมเป้าหมาย, เชื่อม (สตริงย่อยของ S จาก i ถึงขนาดของแหล่งที่มา – 1)
• คืน S

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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