Đếm số lần lặp lại trong C ++

Giả sử chúng ta có hai chuỗi không rỗng s1 và s2 (tối đa 100 ký tự) và hai số n1 và n2 đều nằm trong phạm vi từ 0 đến 106. Bây giờ giả sử các chuỗi S1 và S2, trong đó S1 =[s1, n1] và S2 =[ s2, n2].

S =[s, n] định nghĩa chuỗi S bao gồm n chuỗi liên kết s. Như một ví dụ, ["ab", 4] ="abababab".

Mặt khác, chúng ta cũng xác định rằng chuỗi s1 có thể nhận được từ chuỗi s2 nếu chúng ta loại bỏ một số ký tự khỏi s2 để nó trở thành s1. Vì vậy, "abc" có thể được lấy từ "Abdbec" dựa trên định nghĩa, nhưng không thể lấy được từ "acbbe".

Chúng ta phải tìm số nguyên M lớn nhất sao cho [S2, M] có thể nhận được từ S1.

Vì vậy, nếu đầu vào là s1 ="acb", n1 =4, s2 ="ab", n2 =2, thì đầu ra sẽ là 2

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

cho mỗi ký tự c trong s2
- nếu c không có trong s1, thì -
  - trả về 0
p1:=0, p2:=0, mark:=0
while p1
- c:=s2 [kích thước mod p2 của s2]
- while (s1 [p1 mod size of s1] không bằng c và p1
  - (tăng p1 lên 1)
- (tăng p2 lên 1)
- (tăng p1 lên 1)
- nếu kích thước mod p2 của s2 bằng 0, thì -
  - nếu p2 giống với kích thước của s2, thì -
    - đánh dấu:=p1
  - ngược lại khi kích thước mod p1 của s1 giống với kích thước mod mark của s1 thì -
    - round:=(kích thước của s1 * n1 - p1) / (p1 - mark)
    - p1:=p1 + round * (p1 - mark)
    - p2:=p2 + round * (p2 - kích thước của s2)
trả về p2 / kích thước của s2 / n2

Ví dụ

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

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

Đầu vào

"acb",4,"ab",2

Đếm số lần lặp lại trong C ++

Ví dụ

Đầu vào

Đầu ra