ปั๊มลำดับใน C ++

สมมติว่าเราต้องการสร้างสตริงเป้าหมายด้วยตัวพิมพ์เล็ก

ในตอนแรก เรามีลำดับเป็น n '?' เครื่องหมาย (n คือความยาวของสตริงเป้าหมาย) นอกจากนี้เรายังมีตราประทับอักษรตัวพิมพ์เล็กอีกด้วย

ในแต่ละรอบ เราสามารถวางตราประทับไว้เหนือลำดับ และแทนที่ตัวอักษรทุกตัวใน a ด้วยตัวอักษรที่เกี่ยวข้องกันจากตราประทับนั้น คุณสามารถสร้างได้ถึง 10 * n รอบ ตัวอย่างเช่น ให้พิจารณาลำดับเริ่มต้นคือ "?????" และตราประทับคือ "abc" จากนั้นเราอาจสร้างสตริงเช่น "abc?", "?abc?", "??abc" ในลำดับแรก เลี้ยว

หากลำดับนั้นสามารถประทับตราได้ ให้ส่งคืนอาร์เรย์ของดัชนีด้วยตัวอักษรซ้ายสุดที่ประทับในแต่ละตาแหน่ง หากไม่สามารถทำได้ ให้ส่งคืนอาร์เรย์ว่าง ดังนั้นเมื่อลำดับคือ "ababc" และตราประทับคือ "abc" คำตอบจะเป็นแบบ [0, 2] เพราะเราสร้างได้แบบ "?????" -> "เอบีซี?? -> "abbc".

ดังนั้น หากอินพุตเป็นเหมือน stamp ="abcd", target ="abcdbcd" ผลลัพธ์จะเป็น [3,0]

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

• กำหนดอาร์เรย์ ret

• โอเค :=จริง

• n :=ขนาดของตราประทับ

• tsz :=0

• ขณะที่ตกลงไม่เป็นศูนย์ ให้ทำ -

  • โอเค :=เท็จ

  • x :=0

  • สำหรับการเริ่มต้น sz :=ขนาดของตราประทับ เมื่อ sz> 0, อัปเดต (ลด sz ลง 1) ให้ทำ -

    • สำหรับการเริ่มต้น i :=0 เมื่อฉัน <=ขนาดของตราประทับ ให้อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

      • newStamp :=สตริง '*' ของความยาว i + สตริงย่อยของตราประทับจากดัชนี ito sz-1 + สตริงของ '*' ที่มีขนาดเท่ากับขนาดของตราประทับ

      • pos :=ดัชนีของ newStamp ในเป้าหมาย

      • ในขณะที่ pos อยู่ในเป้าหมาย ให้ทำ -

        • โอเค :=จริง

        • x :=x + sz

        • ใส่ pos ที่ส่วนท้ายของ ret

        • เติมเป้าหมายจากตำแหน่ง pos ถึง pos + ขนาดของตราประทับด้วย '*'

        • pos :=ดัชนีของ newStamp ในเป้าหมาย

  • tsz :=tsz + x

• ย้อนกลับอาร์เรย์ ret

• return (ถ้า tsz เท่ากับขนาดของเป้าหมาย ให้ ret มิฉะนั้น อาร์เรย์ว่างหนึ่งอัน)

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

ตัวอย่าง

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

อินพุต

"abcd", "abcdbcd"

ผลลัพธ์

[3, 0, ]