C++で素数の長さを持つ回文部分文字列を数える方法

このチュートリアルでは、素数の長さを持つ回文部分文字列の個数を求めるプログラムについて解説します。

文字列が1つ与えられ、その中から「回文になっている」かつ「長さが素数である」すべての部分文字列を数えるのが課題です。

解決のアプローチ

この問題は、次の2つの処理を組み合わせることで効率よく解決できます。

• 素数判定： エラトステネスの篩（ふるい）を使い、文字列の長さ以下の素数をあらかじめすべて求めておきます。
• 回文判定： 各素数の長さ j について、すべての開始位置 i から長さ j の部分文字列を取り出し、両端から中央に向かって文字を比較して回文かどうかを確認します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
// 回文かどうかを判定する関数
bool if_palin(string str, int i, int j){
    while (i < j) {
        if (str[i] != str[j])
            return false;
        i++;
        j--;
    }
    return true;
}
// 素数の長さを持つ回文を数える関数
int count_prime(string str, int len){
    bool prime[len + 1];
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false;
    // エラトステネスの篩で素数表を作成
    for (int p = 2; p * p <= len; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= len; i += p)
                prime[i] = false;
        }
    }
    int count = 0;
    // 素数の長さごとに部分文字列を走査
    for (int j = 2; j <= len; j++) {
        if (prime[j]) {
            for (int i = 0; i + j - 1 < len; i++) {
                if (if_palin(str, i, i + j - 1))
                    count++;
            }
        }
    }
    return count;
}
int main(){
    string s = "abccc";
    int len = s.length();
    cout << count_prime(s, len);
    return 0;
}

出力

3

コードの解説

1. 素数表の作成

エラトステネスの篩を用いて、0 から文字列の長さ len までの数値が素数かどうかをブール配列に記録します。0 と 1 は素数ではないため、あらかじめ false を設定しておきます。

2. 回文の判定

if_palin 関数は、指定された範囲 [i, j] の文字列を両端から順に比較していき、1つでも異なる文字があれば false を返します。中央まで一致すれば回文と判定されます。

3. 集計処理

長さが素数であるすべての j に対して、可能なすべての開始位置 i を走査し、回文であればカウントを1つずつ増やしていきます。

実行例の確認

文字列 "abccc" の場合、条件を満たす部分文字列は次の3つです。

• 長さ2："cc"（位置2と位置3の2箇所）
• 長さ3："ccc"（1箇所）

そのため、出力は 3 となります。

計算量

• 時間計算量： 素数の長さごとにすべての部分文字列を回文判定するため、O(n³ / log n) 程度です（n は文字列の長さ）。長さ2以上の素数のみを対象とするため、全部分文字列を調べる O(n³) よりも高速に動作します。
• 空間計算量： 素数表の保存に O(n) を使用します。

より長い文字列を扱う場合は、Manacherのアルゴリズムなどで回文情報を前計算しておくことで、さらに高速化することも可能です。