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

Cho hai chuỗi không rỗng s1, s2 (độ dài ≤ 100) và hai số n1, n2 (0 đến 10^6). Xác định S1 = [s1, n1], S2 = [s2, n2] (chuỗi lặp lại n lần). Chuỗi s1 có thể thu được từ s2 nếu xóa một số ký tự từ s2 để thành s1. Tìm số nguyên M lớn nhất sao cho [S2, M] có thể thu được từ S1.

Ví dụ: s1="acb", n1=4, s2="ab", n2=2 → Kết quả = 2

Phương pháp giải

Kiểm tra mọi ký tự trong s2 có trong s1. Sử dụng hai con trỏ p1, p2 duyệt qua S1, S2. Khi p2 hoàn thành một chu kỳ s2, ghi nhận vị trí p1 (mark). Nếu p1 quay lại cùng vị trí modulo độ dài s1, tính số vòng lặp (round) có thể bỏ qua để tăng tốc.

Ví dụ chương trình

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        for (char 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;
    }
};

int main() {
    Solution ob;
    cout << ob.getMaxRepetitions("acb", 4, "ab", 2);
    return 0;
}

Đầu vào

"acb", 4, "ab", 2

Đầu ra

2