C++で文字列に含まれる重ならない回文部分文字列のペア数を求める方法

問題の概要

文字列が入力として与えられ、その中から重なり合わない（オーバーラップしない）回文部分文字列のペアが何通り作れるかを数えるのが課題です。ここでは、部分文字列 str[i..j] が回文であれば arr[i][j] を true、そうでなければ false とする2次元の真偽値テーブルを利用します。文字列から部分文字列の組み合わせを取り出し、各ペアが条件を満たすかどうかを確認していきます。

例で理解しよう

入力：ABC
出力：重ならない回文部分文字列のペア数は 3
説明：考えられる組み合わせは (A)(B)(C)、(A)(BC)、(AB)(C)、(ABC) となります。

入力：ABCD
出力：重ならない回文部分文字列のペア数は 8
説明：考えられる組み合わせは (A)(B)(C)(D)、(A)(B)(CD)、(A)(BC)(D)、(A)(BCD)、(AB)(C)(D)、(AB)(CD)、(ABC)(D)、(ABCD) です。

アルゴリズムの考え方

• 文字列を入力として受け取り、処理用の関数 pair_count(text) に渡します。
• まずサイズ100の真偽値型2次元配列 arr[ ][ ] を作成し、ボトムアップ方式で値を埋めていきます。同時に入力文字列を文字配列に変換します。
• 回文判定は arr[i+1][j-1] の値をもとに行います。arr[i+1][j-1] が true かつ str[i] == str[j] であれば arr[i][j] を true にし、それ以外は false にします。
• 次に start[ ] と end[ ] を初期化します。start[i] には「インデックス i を含む左側に存在する回文の個数」を、end[i] には「インデックス i を含む右側に存在する回文の個数」を格納します。
• 最後に 0 から str.length() - 1 までループを回し、result に start[i] * end[i + 1] の積を順次加算することで答えを求めます。

実装例

import java.io.*;
import java.util.*;
class tutorialPoint {
    static int SIZE = 100;
    static int pair_count(String str) {
        boolean arr[][] = new boolean[SIZE][SIZE];
        char[] ch = str.toCharArray();
        for (int i = 0; i < ch.length; i++) {
            for (int j = 0; j < ch.length; j++) {
                arr[i][j] = false;
            }
        }
        for (int j = 1; j <= ch.length; j++) {
            for (int i = 0; i <= ch.length - j; i++) {
                if (j <= 2) {
                    if (ch[i] == ch[i + j - 1]) {
                        arr[i][i + j - 1] = true;
                    }
                } else if (ch[i] == ch[i + j - 1]) {
                    arr[i][i + j - 1] = arr[i + 1][i + j - 2];
                }
            }
        }
        int start[] = new int[str.length()];
        int end[] = new int[str.length()];
        start[0] = 1;
        for (int i = 1; i < str.length(); i++) {
            for (int j = 0; j <= i; j++) {
                if (arr[j][i] == true) {
                    start[i]++;
                }
            }
        }
        end[str.length() - 1] = 1;
        for (int i = str.length() - 2; i >= 0; i--) {
            end[i] = end[i + 1];
            for (int j = str.length() - 1; j >= i; j--) {
                if (arr[i][j] == true) {
                    end[i]++;
                }
            }
        }
        int result = 0;
        for (int i = 0; i < str.length() - 1; i++) {
            result = result + start[i] * end[i + 1];
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in); // 例：ABCD
        String text = scan.next();
        System.out.println("Count pairs of non-overlapping palindromic sub-strings is\t" + pair_count(text));
    }
}

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

出力結果

Count pairs of non-overlapping palindromic sub-strings is 8