Thêm thẻ in đậm trong chuỗi trong C ++

Giả sử chúng ta có một chuỗi s và một danh sách các chuỗi được gọi là dict, chúng ta phải thêm một cặp đóng thẻ chữ đậm và để bọc các chuỗi con trong s tồn tại trong dict đó. Khi hai chuỗi con như vậy chồng lên nhau, thì chúng ta chỉ phải quấn chúng lại với nhau bằng một cặp thẻ in đậm đã đóng. Ngoài ra, nếu hai chuỗi con được bao bọc bởi các thẻ in đậm liên tiếp, chúng ta cần kết hợp chúng.

Vì vậy, nếu đầu vào giống như s ="abcxyz123" dict là ["abc", "123"], thì đầu ra sẽ là " abc xyz 123 "

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của s

• Xác định mảng đậm có kích thước n

• ret:=chuỗi trống

• để khởi tạo i:=0, end:=0, khi tôi

  • để khởi tạo j:=0, khi j

    • nếu chuỗi con của s từ chỉ mục (i đến kích thước của dict [j] - 1) giống như dict [j], thì -

      • end:=tối đa của end và i + kích thước của dict [j]

  • bold [i]:=end> ​​i

• để khởi tạo i:=0, khi i

  • nếu in đậm [i] bằng 0 thì -

    • ret:=ret + s [i]

    • j:=i + 1

    • Bỏ qua phần sau, chuyển sang phần tiếp theo

  • j:=i

  • while (j

    • (tăng j lên 1)

  • ret:=chuỗi con của ret từ chỉ mục i đến j - i - 1 nối "" nối s

• trả lại ret

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string addBoldTag(string s, vector<string>& dict) {
      int n = s.size();
      vector<int> bold(n);
      string ret = "";
      for (int i = 0, end = 0; i < s.size(); i++) {
         for (int j = 0; j < dict.size(); j++) {
            if (s.substr(i, dict[j].size()) == dict[j]) {
               end = max(end, i + (int)dict[j].size());
            }
         }
         bold[i] = end > i;
      }
      int j;
      for (int i = 0; i < s.size(); i = j) {
         if (!bold[i]) {
            ret += s[i];
            j = i + 1;
            continue;
         }
         j = i;
         while (j < s.size() && bold[j])
         j++;
         ret += "<b>" + s.substr(i, j - i) + "</b>";
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<string> v = {"abc","123"};
   cout << (ob.addBoldTag("abcxyz123", v));
}

"abcxyz123", ["abc","123"]

<b>abc</b>xyz<b>123</b>