1. 概要

このクイックチュートリアルでは、パリンドロームである特定の文字列内のすべてのサブストリングを見つけるためのさまざまなアプローチを実行します。 また、各アプローチの時間計算量にも注意します。

2. ブルートフォースアプローチ

このアプローチでは、入力文字列を繰り返し処理して、すべてのサブ文字列を検索します。 同時に、サブストリングが回文であるかどうかを確認します。

public Set<String> findAllPalindromesUsingBruteForceApproach(String input) {
    Set<String> palindromes = new HashSet<>();
    for (int i = 0; i < input.length(); i++) {
        for (int j = i + 1; j <= input.length(); j++) {
            if (isPalindrome(input.substring(i, j))) {
                palindromes.add(input.substring(i, j));
            }
        }
    }
    return palindromes;
}

上記の例では、部分文字列をその逆文字列と比較して、それが回文であるかどうかを確認します。

private boolean isPalindrome(String input) {
    StringBuilder plain = new StringBuilder(input);
    StringBuilder reverse = plain.reverse();
    return (reverse.toString()).equals(input);
}

もちろん、他のいくつかのアプローチから簡単に選択できます。

このアプローチの時間計算量はO(n ^ 3)です。これは小さな入力文字列では許容できるかもしれませんが、大量のテキストの回文をチェックする場合は、より効率的なアプローチが必要になります。 。

3. 集中化アプローチ

集中化アプローチの考え方は、各文字をピボットと見なし、両方向に拡張してパリンドロームを見つけることです

左側と右側の文字が一致する場合にのみ拡張し、文字列を回文と見なします。 それ以外の場合は、次の文字に進みます。

各キャラクターを回文の中心と見なす簡単なデモンストレーションを見てみましょう。

public Set<String> findAllPalindromesUsingCenter(String input) {
    Set<String> palindromes = new HashSet<>();
    for (int i = 0; i < input.length(); i++) {
        palindromes.addAll(findPalindromes(input, i, i + 1));
        palindromes.addAll(findPalindromes(input, i, i));
    }
    return palindromes;
}

上記のループ内で、両方向に拡張して、すべてのパリンドロームのセットを各位置の中央に配置します。 メソッドfindPalindromesをループ内で2回呼び出すことにより、偶数と奇数の両方の長さのパリンドロームを検索します

private Set<String> findPalindromes(String input, int low, int high) {
    Set<String> result = new HashSet<>();
    while (low >= 0 && high < input.length() && input.charAt(low) == input.charAt(high)) {
        result.add(input.substring(low, high + 1));
        low--;
        high++;
    }
    return result;
}

このアプローチの時間計算量はO(n ^ 2)です。これはブルートフォースアプローチよりも改善されていますが、次のセクションで説明するように、さらに改善することができます。

4. マナチャーのアルゴリズム

Manacherのアルゴリズムは、線形時間で最長のパリンドローム部分文字列を検出します。 このアルゴリズムを使用して、回文であるすべてのサブストリングを検索します。

アルゴリズムに飛び込む前に、いくつかの変数を初期化します。

まず、結果の文字列を文字配列に変換する前に、入力文字列を最初と最後に境界文字で保護します。

String formattedInput = "@" + input + "#";
char inputCharArr[] = formattedInput.toCharArray();

次に、2つの行を持つ2次元配列 radius を使用します。1つは奇数の長さのパリンドロームの長さを格納し、もう1つは偶数の長さのパリンドロームの長さを格納します。

int radius[][] = new int[2][input.length() + 1];

次に、入力配列を反復処理して、位置 i を中心とする回文の長さを見つけ、この長さを radius [][]に格納します。

Set<String> palindromes = new HashSet<>();
int max;
for (int j = 0; j <= 1; j++) {
    radius[j][0] = max = 0;
    int i = 1;
    while (i <= input.length()) {
        palindromes.add(Character.toString(inputCharArr[i]));
        while (inputCharArr[i - max - 1] == inputCharArr[i + j + max])
            max++;
        radius[j][i] = max;
        int k = 1;
        while ((radius[j][i - k] != max - k) && (k < max)) {
            radius[j][i + k] = Math.min(radius[j][i - k], max - k);
            k++;
        }
        max = Math.max(max - k, 0);
        i += k;
    }
}

最後に、配列 radius [] [] をトラバースして、各位置を中心とするパリンドロームサブストリングを計算します。

for (int i = 1; i <= input.length(); i++) {
    for (int j = 0; j <= 1; j++) {
        for (max = radius[j][i]; max > 0; max--) {
            palindromes.add(input.substring(i - max - 1, max + j + i - 1));
        }
    }
}

このアプローチの時間計算量はO(n)です。

5. 結論

この簡単な記事では、回文である部分文字列を見つけるためのさまざまなアプローチの時間計算量について説明しました。

いつものように、例の完全なソースコードは、GitHubから入手できます。