C++で文字列内の特殊な回文を数える方法

問題の概要

文字列 str が与えられたとき、str の部分文字列の中から「特殊な回文」に該当するものをすべて数えることを考えます。ここで特殊な回文とは、長さが1より大きく、すべての文字が同一であるか、あるいは中央の文字だけが異なる文字列のことです。

例えば、文字列が "baabaa" の場合、元の文字列の部分文字列となっている特殊な回文は "aa"、"aabaa"、"aba"、"aa" となります。

具体例で確認してみましょう。

例1

• 入力: str = "abccdcdf"
• 出力: 文字列内の特殊な回文の数 − 3
• 説明: 特殊な回文となる部分文字列は "cc"、"cdc"、"dcd" です。

例2

• 入力: str = "baabaab"
• 出力: 文字列内の特殊な回文の数 − 4
• 説明: 特殊な回文となる部分文字列は "aa"、"aabaa"、"aba"、"aa" です。

アルゴリズムの考え方

このプログラムでは、以下の手順で特殊な回文を効率的に数えます。

1. 対象となる文字列を作成し、その長さを求めます。データを関数に渡して以降の処理を行います。
2. 一時変数 count と i を宣言し、0 で初期化します。
3. 文字列と同じサイズの配列 arr を作成し、0 で初期化します。
4. i が文字列の長さ未満である間、while ループを繰り返します。
5. ループ内では、変数 total を 1、変数 j を i + 1 に設定します。
6. str[i] == str[j] かつ j が文字列の長さ未満である間、内側の while ループを回します。
7. 内側のループでは total と j をそれぞれ1ずつ増やします。
8. count に total * (total + 1) / 2 を加算し、arr[i] に total を、i に j を代入します。これにより、同じ文字が連続する区間ごとの回文数をまとめて計算できます。
9. 次に、j を 1 から文字列の長さまで for ループで走査します。
10. str[j] == str[j-1] の場合は、arr[j] を arr[j-1] に設定します。
11. 変数 temp に str[j-1] を格納し、j > 0 かつ j < len - 1 かつ temp == str[j+1] かつ str[j] != temp が成り立つ場合(つまり中央の文字だけが異なる回文の中心を検出した場合)、count に min(arr[j-1], arr[j+1]) を加算します。
12. 最後に count から文字列の長さを引きます(長さ1の部分文字列は条件を満たさないため除外)。
13. count を返し、結果を出力します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int count_palindromes(string str, int len){
   int count = 0, i = 0;
   int arr[len] = { 0 };
   while (i < len){
      int total = 1;
      int j = i + 1;
      while (str[i] == str[j] && j < len){
         total++;
         j++;
      }
      count += (total * (total + 1) / 2);
      arr[i] = total;
      i = j;
   }
   for (int j = 1; j < len; j++){
      if (str[j] == str[j - 1]){
         arr[j] = arr[j - 1];
      }
      int temp = str[j - 1];
      if (j > 0 && j < (len - 1) && (temp == str[j + 1] && str[j] != temp)){
         count += min(arr[j-1], arr[j+1]);
      }
   }
   count = count - len;
   return count;
}
int main(){
   string str = "bcbaba";
   int len = str.length();
   cout<<"Count of special palindromes in a String are: "<< count_palindromes(str, len);
   return 0;
}

実行結果

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

Count of special palindromes in a String are: 3

まとめ

このアルゴリズムは、連続する同一文字の区間ごとに組み合わせの数 n*(n+1)/2 を用いて一括でカウントすることで、全部分文字列を総当たりするよりも効率的に特殊な回文を数えられます。さらに、左右の文字が対称で中央だけが異なるパターン("cdc" や "aabaa" など)については、事前に計算した連続文字数配列 arr を参照して min 関数で加算しています。計算量は O(N) と非常に効率的で、長い文字列に対しても高速に動作します。