Đánh dấu chuỗi trong C++

Muốn tạo chuỗi target chữ thường. Ban đầu có n dấu '?' (n = độ dài target). Có stamp chữ thường. Mỗi lượt đặt stamp lên chuỗi, thay thế ký tự tương ứng. Tối đa 10*n lượt. Trả về mảng chỉ số trái nhất của stamp mỗi lượt. Không thể thì trả về mảng rỗng.

Ví dụ: stamp="abcd", target="abcdbcd" → [3,0]. "?????" → "abc??" (stamp tại 0) → "ababc" (stamp tại 2). Nhưng output [3,0] có nghĩa ngược lại: stamp tại 3 rồi 0.

Giải pháp

Thuật toán ngược (reverse stamping) - biến target thành toàn '*':

• Khởi tạo ret = [], ok = true, tsz = 0
• While ok:
  • ok = false, x = 0
  • Duyệt sz từ len(stamp) xuống 1 (độ dài khớp)
  • Duyệt i từ 0 đến len-stamp (vị trí bắt đầu khớp)
  • Tạo newStamp: i dấu '*' + stamp.substr(i, sz) + (len-sz-i) dấu '*'
  • Tìm newStamp trong target, lặp:
    • ok = true, x += sz
    • Thêm vị trí vào ret
    • Điền '*' vào target[pos..pos+len]
    • Tìm tiếp
• tsz += x

Ví dụ mã C++

#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>(); 
    } 
}; 

int main() { 
    Solution ob; 
    print_vector(ob.movesToStamp("abcd", "abcdbcd")); 
    return 0; 
}

Đầu vào

"abcd", "abcdbcd"

Đầu ra

[3, 0, ]