22

入力が「abba」の場合、可能な回文は a、b、b、a、bb、abba です。
文字列が回文かどうかを判断するのは簡単だということは理解しています。次のようになります。

public static boolean isPalindrome(String str) {
 int len = str.length();
 for(int i=0; i<len/2; i++) {
     if(str.charAt(i)!=str.charAt(len-i-1) {
         return false;
     }
 return true;  
}

しかし、パリンドローム部分文字列を見つける効率的な方法は何ですか?

4

9 に答える 9

9

したがって、それぞれの個別の文字はすでに回文です。したがって、すでに N + 1 回文があります。ここで、N は個別の文字 (および空の文字列) の数です。1回の実行でそれを行うことができます-O(N)。

ここで、重要な回文の場合、文字列の各ポイントが潜在的な回文の中心になるようにテストできます-両方の方向に成長します-Valentin Ruanoが提案したものです.
各テストは O(N) であり、可能な「中心」の数も O(N) であるため、このソリューションには O(N^2) がかかりcenterます。

Manacherのアルゴリズムに基づいて、問題に対するO(N)ソリューションもあることに注意してください(記事では「最長回文」について説明していますが、アルゴリズムを使用してそれらすべてをカウントできます)。

于 2013-11-05T23:57:30.040 に答える
5

この問題を解決するのに役立つ独自のロジックを思いつきました。幸せなコーディング.. :-)

System.out.println("Finding all palindromes in a given string : ");
        subPal("abcacbbbca");

private static void subPal(String str) {
        String s1 = "";
        int N = str.length(), count = 0;
        Set<String> palindromeArray = new HashSet<String>();
        System.out.println("Given string : " + str);
        System.out.println("******** Ignoring single character as substring palindrome");
        for (int i = 2; i <= N; i++) {
            for (int j = 0; j <= N; j++) {
                int k = i + j - 1;
                if (k >= N)
                    continue;
                s1 = str.substring(j, i + j);
                if (s1.equals(new StringBuilder(s1).reverse().toString())) {
                    palindromeArray.add(s1);
                }
            }

        }
        System.out.println(palindromeArray);
        for (String s : palindromeArray)
            System.out.println(s + " - is a palindrome string.");
        System.out.println("The no.of substring that are palindrome : "
                + palindromeArray.size());
    }

Output:-
Finding all palindromes in a given string : 
Given string : abcacbbbca
******** Ignoring single character as substring palindrome ********
[cac, acbbbca, cbbbc, bb, bcacb, bbb]
cac - is a palindrome string.
acbbbca - is a palindrome string.
cbbbc - is a palindrome string.
bb - is a palindrome string.
bcacb - is a palindrome string.
bbb - is a palindrome string.
The no.of substring that are palindrome : 6
于 2013-12-17T18:47:03.620 に答える