นับการทำซ้ำใน C ++

สมมติว่าเรามีสตริงที่ไม่ว่างสองสตริง s1 และ s2 (สูงสุด 100 อักขระ) และตัวเลขสองตัว n1 และ n2 ทั้งคู่อยู่ในช่วง 0 ถึง 106 ทีนี้ สมมติว่าสตริง S1 และ S2 โดยที่ S1=[s1,n1] และ S2=[ s2,n2].

S =[s,n] กำหนดสตริง S ซึ่งประกอบด้วย n สตริงที่เชื่อมต่อ s ตัวอย่าง ["ab", 4] ="abababab".

ในทางกลับกัน เรายังกำหนดด้วยว่าสตริง s1 สามารถรับได้จากสตริง s2 หากเราลบอักขระบางตัวออกจาก s2 ซึ่งจะทำให้กลายเป็น s1 ดังนั้น "abc" สามารถหาได้จาก "abdbec" ตามคำจำกัดความ แต่ไม่สามารถหาได้จาก "acbbe"

เราต้องหาจำนวนเต็ม M สูงสุดที่ [S2,M] หาได้จาก S1

ดังนั้น หากอินพุตเป็น s1="acb", n1=4, s2="ab", n2=2 ผลลัพธ์จะเป็น 2

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

• สำหรับแต่ละอักขระ c ใน s2

  • ถ้า c ไม่ได้อยู่ใน s1 แล้ว −

    • คืนค่า 0

• p1 :=0, p2 :=0, เครื่องหมาย :=0

• ในขณะที่ p1 <ขนาดของ s1 ทำ −

  • c :=s2[ขนาด mod p2 ของ s2]

  • ในขณะที่ (s1[p1 ขนาด mod ของ s1] ไม่เท่ากับ c และ p1 <ขนาดของ s1 *n1) ให้ทำ -

    • (เพิ่ม p1 ขึ้น 1)

  • (เพิ่ม p2 ขึ้น 1)

  • (เพิ่ม p1 ขึ้น 1)

  • ถ้า p2 mod size ของ s2 เท่ากับ 0 ดังนั้น −

    • ถ้า p2 เท่ากับขนาดของ s2 แล้ว −

      • มาร์ค :=p1

    • มิฉะนั้นเมื่อ p1 mod size ของ s1 เท่ากับ mark mod size ของ s1 ดังนั้น −

      • รอบ :=(ขนาด s1 * n1 - p1) / (p1 - เครื่องหมาย)

      • p1 :=p1 + รอบ * (p1 - เครื่องหมาย)

      • p2 :=p2 + รอบ * (p2 - ขนาดของ s2)

• ส่งคืน p2 / ขนาดของ s2 / n2

ตัวอย่าง

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int getMaxRepetitions(string s1, int n1, string s2, int n2) {
      for (auto c : s2) {
         if (s1.find(c) == string::npos)
            return 0;
      }
      int p1 = 0, p2 = 0, mark = 0;
      while (p1 < s1.length() * n1) {
         char c = s2[p2 % s2.length()];
         while (s1[p1 % s1.length()] != c && p1 <s1.length() * n1)
         p1++;
         p2++;
         p1++;
         if (p2 % s2.length() == 0) {
            if (p2 == s2.length()) {
               mark = p1;
            }
            else if (p1 % s1.length() == mark % s1.length()) {
               int round = (s1.length() * n1 - p1) / (p1 - mark);
               p1 += round * (p1 - mark);
               p2 += round * (p2 - s2.length());
            }
         }
      }
      return p2 / s2.length() / n2;
   }
};
main() {
   Solution ob;
   cout << (ob.getMaxRepetitions("acb",4,"ab",2));
}

อินพุต

"acb",4,"ab",2

ผลลัพธ์

2