Đếm ước chung của hai chuỗi trong C++

Cho hai chuỗi numo, demo. Chuỗi con sub1 là ước của str nếu lặp lại sub1 tạo ra str. Đếm ước chung của hai chuỗi.

Điều kiện ước chung

• Độ dài sub1 chia hết độ dài cả hai chuỗi.
• sub1 là tiền tố chung.
• Lặp sub1 tạo ra đúng cả hai chuỗi.

Ví dụ hoàn chỉnh

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

int verify(string str, int val) {
    int length = str.length();
    for (int i = 0; i < length; i++) {
        if (str[i] != str[i % val])
            return 0;
    }
    return 1;
}

int common_divisor(string numo, string demo) {
    int count = 0;
    int numo_size = numo.size();
    int demo_size = demo.size();
    int min_val = min(numo_size, demo_size);
    for (int i = 1; i <= min_val; i++) {
        if (numo_size % i == 0 && demo_size % i == 0) {
            if (numo.substr(0, i) == demo.substr(0, i)) {
                if (verify(numo, i) == 1 && verify(demo, i) == 1)
                    count++;
            }
        }
    }
    return count;
}

int main() {
    string numo = "abababab";
    string demo = "abababababababab";
    cout << "Số ước chung: " << common_divisor(numo, demo);
    return 0;
}

Kết quả

Số ước chung: 3