นับตัวหารร่วมของสตริงสองตัว (Common String Divisors) ใน C++

โจทย์: ให้สตริงสองตัว numo และ demo ต้องการหาจำนวนสตริงที่เป็น "ตัวหาร" ของทั้งสองสตริง

นิยามตัวหารของสตริง

สตริง s เป็นตัวหารของ t ก็ต่อเมื่อ t สามารถสร้างได้โดยการซ้ำ s หลายครั้ง
เช่น: "abc" เป็นตัวหารของ "abcabcabc"

เงื่อนไขที่จำเป็น

1. ความยาว s ต้องหารความยาว t ลงตัว
2. s ต้องเป็น prefix ของ t
3. การซ้ำ s ต้องสร้าง t ได้ทุกตัวอักษร

อัลกอริทึม

1. หาความยาวน้อยที่สุดของสองสตริง
2. ลองความยาว i = 1 ถึง min_len
3. ถ้า i หารความยาวทั้งสองลงตัว และ prefix ตรงกัน
4. ตรวจสอบว่า prefix ความยาว i เป็นตัวหารของทั้งสองสตริง

ฟังก์ชันตรวจสอบ

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

ฟังก์ชันหลัก

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

ตัวอย่างเต็ม

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

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

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

int main() {
    string numo = "abababab";
    string demo = "abababababababab";
    cout << "Count: " << common_divisor(numo, demo);
    return 0;
}

ผลลัพธ์

Count the number of common divisors of the given strings are: 3

ตัวหารร่วม: "ab", "abab", "abababab" (3 ตัว) - หมายเหตุ: โค้ดเดิมแสดงผล 3 แต่คำอธิบายเขียน 2