C++で指定インデックス範囲内の回文部分文字列の個数を求める方法

文字列と、startからendまでの範囲が与えられたとき、その範囲内に存在する回文（パリンドローム）部分文字列の個数を計算するのが本記事のテーマです。回文とは、「nitin」や「aba」のように、前から読んでも後ろから読んでも同じになる文字列のことを指します。

例

入力 − InputString = "cccaabbbdee"、start = 2、end = 6

出力 − 指定インデックス範囲内の回文部分文字列の個数：7

説明 − 文字列と範囲が与えられているため、startポインタの位置2（'c'）からendポインタの位置6（'b'）まで文字列を走査します。対象となる部分文字列は「caabb」です。この中に含まれる回文部分文字列は、'c'、'a'、'a'、'b'、'b'、'aa'、'bb' の7つとなります。

入力 − InputString = "lioaabbbdee"、start = 0、end = 2

出力 − 指定インデックス範囲内の回文部分文字列の個数：3

説明 − startポインタの位置0（'l'）からendポインタの位置2（'o'）まで走査すると、対象となる部分文字列は「lio」です。この中の回文部分文字列は 'l'、'i'、'o' の3つとなります。

プログラムで採用しているアプローチ

• 任意のサイズの文字列と、変数startからendまでの範囲を宣言します。
• データを関数 palindrome_index(arr, InputString) に渡し、以降の処理を行います。
• 関数内で、文字列の長さに対応するサイズの2次元配列 check を宣言します。
• i を0から配列の長さまでループさせます。
• その内部で、j を0から配列の長さまでさらにループさせます。
• ループ内では check[i][j] = 0 および arr[i][j] = 0 を設定します。
• i を length - 1 から0以上となる間、逆順にループさせます。
• ループ内で check[i][i] と arr[i][i] を1に設定した後、j を i + 1 から配列の長さまでループさせます。
• ループ内で、i 番目の文字と j 番目の文字が一致し、かつ (i + 1 > j - 1 または check[i + 1][j - 1] != 0) が成り立つ場合は check[i][j] を1に、そうでなければ0に設定します。続いて arr[i][j] = arr[i][j - 1] + arr[i + 1][j] - arr[i + 1][j - 1] + check[i][j] を計算します。
• 最後に、start と end をインデックスとして2次元配列の値を出力します。

例

import java.io.*;
class testqwe {
    static void palindrome_index(int arr[][], String s) {
        int length = s.length();
        int[][] check = new int[length + 1][length + 1];
        for (int i = 0; i <= length; i++) {
            for (int j = 0; j <= length; j++) {
                check[i][j] = 0;
                arr[i][j] = 0;
            }
        }

        for (int i = length - 1; i >= 0; i--) {
            check[i][i] = arr[i][i] = 1;
            for (int j = i + 1; j < length; j++) {
                if(s.charAt(i) == s.charAt(j) && (i + 1 > j - 1 || (check[i + 1][j - 1]) != 0)) {
                    check[i][j] = 1;
                } else {
                    check[i][j] = 0;
                }
                arr[i][j] = arr[i][j - 1] + arr[i + 1][j] - arr[i + 1][j - 1] + check[i][j];
            }
        }
    }
    public static void main(String args[]) {
        String InputString = "cccaabbbdee";
        int[][] arr;
        arr = new int[50][50];
        palindrome_index(arr, InputString);
        int start = 2;
        int end = 6;
        System.out.println("Count of Palindromic substrings in an Index range " + arr[start][end]);
    }
}

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

出力

Count of Palindromic substrings in an Index range 7