Đóng dấu trình tự trong C ++

Giả sử chúng ta muốn tạo một chuỗi đích gồm các chữ cái thường.

Lúc đầu, chúng ta có dãy là n '?' dấu (n là độ dài của chuỗi đích). Chúng tôi cũng có một con tem gồm các chữ cái thường.

Trên mỗi lượt, chúng ta có thể đặt con tem trên dãy và thay thế mọi chữ cái trong con bằng chữ cái tương ứng từ con tem đó. Bạn có thể thực hiện tối đa 10 * n lượt. Ví dụ, hãy xem xét chuỗi ban đầu là "?????" và dấu là "abc", sau đó chúng ta có thể tạo các chuỗi như "abc ??", "? Abc?", "?? abc" trong đầu tiên rẽ.

Nếu chuỗi có thể được đóng dấu, thì trả về một mảng của chỉ số với chữ cái ngoài cùng bên trái được đóng dấu ở mỗi lượt. Nếu không được thì trả về một mảng trống. Vì vậy, khi dãy là "ababc", và dấu là "abc", thì câu trả lời có thể giống như [0, 2], Bởi vì chúng ta có thể tạo thành như "?????" -> "abc ??" -> "ababc".

Vì vậy, nếu đầu vào giống như tem ="abcd", target ="abcdbcd", thì đầu ra sẽ là [3,0]

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

• Xác định ret mảng

• ok:=true

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

• tsz:=0

• trong khi ok là khác 0, làm -

  • ok:=false

  • x:=0

  • để khởi tạo sz:=kích thước của tem, khi sz> 0, cập nhật (giảm sz đi 1), thực hiện -

    • để khởi tạo i:=0, khi i <=kích thước của tem, hãy cập nhật (tăng i lên 1), thực hiện -

      • newStamp:=một chuỗi '*' có độ dài i + chuỗi con tem từ chỉ mục ito sz-1 + một chuỗi '*' có kích thước bằng với kích thước của tem

      • pos:=index of newStamp trong target

      • trong khi pos hiện diện trong target, do -

        • ok:=true

        • x:=x + sz

        • chèn pos vào cuối ret

        • điền mục tiêu từ vị trí pos đến pos + kích thước của tem với '*'.

        • pos:=index of newStamp trong target

  • tsz:=tsz + x

• đảo ngược mảng ret

• return (nếu tsz giống với kích thước của target thì hãy ret, nếu không sẽ là một mảng trống)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   } cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> movesToStamp(string stamp, string target) {
      vector<int> ret;
      bool ok = true;
      int n = stamp.size();
      int tsz = 0;
      while (ok) {
         ok = false;
         int x = 0;
         for (int sz = stamp.size(); sz > 0; sz--) {
            for (int i = 0; i <= stamp.size() - sz; i++) {
               string newStamp = string(i, '*') +
               stamp.substr(i, sz) + string(stamp.size() - sz - i, '*');
               int pos = target.find(newStamp);
               while (pos != string::npos) {
                  ok = true;
                  x += sz;
                  ret.push_back(pos);
                  fill(target.begin() + pos, target.begin() +
                  pos + stamp.size(), '*');
                  pos = target.find(newStamp);
               }
            }
         }
         tsz += x;
      }
      reverse(ret.begin(), ret.end());
      return tsz == target.size() ? ret : vector<int>();
   }
};
main(){
   Solution ob;
   print_vector(ob.movesToStamp("abcd", "abcdbcd"));
}

Đầu vào

"abcd", "abcdbcd"

Đầu ra

[3, 0, ]