C++で2つの文字列に共通する「文字列の約数」の個数を数える方法

本記事では、2つの文字列 numo と demo を入力として受け取り、両方の文字列に共通する「約数」の個数を求めるC++プログラムを紹介します。

ここでいう文字列の約数とは、その部分文字列を任意の回数繰り返すことで元の文字列を完全に構成できるような部分文字列のことです。例えば、str = "abcabcabc" の場合、"abc" を3回繰り返すことで元の文字列になるため、"abc" は str の約数です。

入力例と出力例

例1

入力:

numo = "abababab"
demo = "abababababababab"

出力:

与えられた文字列の共通約数の個数: 3

説明:
両方の文字列を生成できる共通の約数は、「ab」「abab」「abababab」の3つです。

例2

入力:

numo = "pqqppqqp"
demo = "pqpq"

出力:

与えられた文字列の共通約数の個数: 0

説明:
共通の約数は存在しません。numo の約数は「pqqp」(および文字列自身)、demo の約数は「pq」(および文字列自身)だけで、重なるものがありません。

アルゴリズムの考え方

ある部分文字列 sub1 が文字列 str の約数になるためには、次の条件をすべて満たす必要があります。

• str の接頭辞(先頭から始まる部分文字列)であること
• その長さが str の長さを割り切ること
• 実際に繰り返したときに str が再現できること

この条件を両方の文字列に対してチェックし、条件を満たす長さごとにカウントを増やしていきます。

処理の手順

1. 文字列 numo と demo を入力として受け取ります。
2. 関数 verify(string str, int val) は、先頭から val 文字分の部分文字列を繰り返すことで str 全体が生成できる場合に 1 を返します。
3. 関数 common_divisor(string numo, string demo) は、2つの文字列の共通約数の個数を返します。
4. カウント用変数を 0 で初期化します。
5. 両文字列の長さを求め、短い方の長さを min_val に格納します。
6. for ループで i = 1 から min_val まで走査します。
7. i が両方の文字列の長さを割り切り、かつ接頭辞が一致する(numo.substr(0, i) == demo.substr(0, i))場合に絞り込みます。
8. verify() を呼び出し、先頭 i 文字の部分文字列が両方の文字列の約数になっているかを確認します。
9. verify(numo, i) と verify(demo, i) がどちらも 1 を返したら、カウントを 1 増やします。
10. ループ終了後、カウントを結果として返します。

C++での実装例

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

// 先頭 val 文字の繰り返しで str が構成できるかを判定する
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;
}

// 2つの文字列の共通約数の個数を数える
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){
            if(demo_size % i == 0){
                if(numo.substr(0, i) == demo.substr(0, i)){
                    if(verify(numo, i)==1){
                        if(verify(demo, i)==1){
                            count++;
                        }
                    }
                }
            }
        }
    }
    return count;
}

int main(){
    string numo = "abababab";
    string demo = "abababababababab";
    cout<<"Count the number of common divisors of the given strings are: "
       <<common_divisor(numo, demo);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

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

計算量について

外側のループは短い方の文字列の長さ min(n, m) 回実行され、各ステップの verify() は文字列全体を走査するため O(n + m) のコストがかかります。したがって、全体の時間計算量は O(min(n, m) × (n + m)) 程度です。追加のデータ構造を使用しないため、空間計算量は O(1) となります。