0

我试图在 Java 中找到一个子回文。但是下面的代码没有提供正确的输出。

public static void main(String[] args)
{
    Scanner in = new Scanner(System.in);
    in.useDelimiter("\n");
    String text = in.next();
    int start = 0;
    int end = 0;

    int i = 0;
    int j = 0;
    while(i <= text.length())
    {
        j = i+1;
        while(j < text.length())
        {
            if(text.substring(i, j).equals(reverse(text.substring(i, j))))
            {
                if(j-i > end-start)
                {
                    start = i; end = j;
                }   
            }
            j++;
        }
        i++;
    }
    System.out.println(start + " : " + end);
}
static String reverse(String s)
{
    return new StringBuffer(s).reverse().toString();
}

样本输出：

apros tda adda
7 : 12
after the ostso
11 : 14
att feref
5 : 8

以上都是错误的。

PS：我知道这不是一个有效的算法。

4

3 回答 3

0

有两个问题：

1：我在上面的评论中提到的那个：

if(j-i > end-start) {
    start = i;
    end = j;
}

2：让j一直到正文结束：

while(j <= text.length())

这是另一种可能性，既然您已经修复了代码，如果您需要，我可以为您提供一个更优化的替代解决方案。找到最大的回文基本上是在一个字符串和它的反向之间找到最大的常用词。所以从反转字符串开始（即text2）。遍历文本 (i)，然后有一个表示长度减小的子迭代（从 text.length()-i 下降到 0。如果您在 text2 中找到当前单词，那么您就找到了回文。您只需需要评估它是否是最大的。

一个明显的额外优化是，如果您已经找到回文，则长度的子迭代不需要降至零。

    String text = "absoopoo";       
    String text2 = new StringBuffer(text).reverse().toString();

    int start = 0;
    int end = -1;

    for(int i=0; i<text.length(); i++) {
        for(int length=text.length()-i; length > (end-start); length--) {
            String sub = text.substring(i, i+length);
            if(text2.indexOf(sub) >= 0) {
                start = i;
                end = start+length;
            }
        }
    }

    System.out.println(start + " : " + end+ " => "+text.substring(start, end));
于 2012-06-29T14:45:05.917 回答
0

终于让它工作了。

public static void main(String[] args)
{
    Scanner in = new Scanner(System.in);
    in.useDelimiter("\n");
    String text = in.next();

    int start = 0;
    int end = 0;

    int i = 0;
    int j = 0;
    while(i < text.length())
    {
        j = i;
        while(j <= text.length())
        {
            if(text.substring(i, j).equals(reverse(text.substring(i, j))))
            {
                if(j-i > 1 && j-i > end-start)
                {
                    start = i; 
                    end = j;
                }   
            }
            j++;
        }
        i++;
    }
    System.out.println(start + " : " + (end-1));
}
static String reverse(String s)
{
    return new StringBuffer(s).reverse().toString();
}

这是一个更优化的版本。这是基于此

public static void main(String[] args)
{
    Scanner in = new Scanner(System.in);
    in.useDelimiter("\n");
    char[] text = in.next().toCharArray();

    int start = 0;
    int end = 0;
    ArrayList<Integer[]> list = new ArrayList<Integer[]>();
    for( ;start<text.length; start++)
    {
        for(end=start; end<=start+1; end++)
        {
            list.add(grow(text, start, end));
        }
    }
    for(Integer[] v: list)
        System.out.println(v[0] +" : "+v[1]);
    findmax(list);
}
static Integer[] grow(char[] text, int start, int end)
{
    while(start>0 && end < text.length && text[start-1]==text[end])
    {
        start--;
        end++;
    }
    return new Integer[]{start, end};
}
static void findmax(ArrayList<Integer[]> list)
{
    int i=0; int j=0;
    for(Integer[] v: list)
    {
        if(v[1]-v[0]>j-i)
        {
            i = v[0];
            j = v[1];
        }
    }
    System.out.println(i+" "+j);
}
于 2012-06-29T16:40:14.693 回答
0

让我们知道您是否需要它（以及它是否具有良好的性能）：

/** Transmitted max size between to parses */
static int maxSize = 0;

/**
 * Said if the String is a palindrome.
 * 
 * @param s
 *            sentence to parse.
 */
static void singlePalindrome(final String s) {

    System.out.println("singlePalindrome: " + s);
    final char[] word = s.toCharArray();
    final int t = word.length;
    boolean ok = true;
    for (int i = t / 2; i > 0; i--) {

        if (word[i - 1] != word[word.length - i]) {

            ok = false;
            break;
        }

        System.out.println((i - 1) + ":" + word[i - 1] + "\t" + (t - i)
            + ":" + word[t - i]);
    }

    System.out.println("It is " + (true == ok ? "" : "NOT ")
        + "a palindrome.");
}

/**
 * Find all palindromes included anywhere in a sentence, with two search
 * phases from left to right and right to left. Then keep the biggest one *
 * 
 * @param sentence
 *            to parse
 * @param len
 *            minimal size of palindrome(s) to find.
 */
static void palindromeNested(final String sentence, final int len) {
    System.out.println(len + " = minimal size for palindromeNested(..): "
        + sentence);
    int debS = 2;
    String max = null;

    while (debS <= sentence.length()) {

        int i = debS / 2;
        int cpt = 0;
        for (; i <= debS; i++) {
            ++cpt;
            if (sentence.charAt(i) == sentence.charAt(debS - i)) {
                if (cpt >= len) {
                    final String sTmp = (i > debS - i) //
                        ? sentence.substring(debS - i, i + 1) //
                        : sentence.substring(i, debS - i + 1);

                    final int maxTmp = sTmp.length();
                    if (maxTmp > maxSize) {
                        maxSize = maxTmp;
                        max = sTmp;
                        System.out.println(maxTmp + "\t" + max);
                    }

                    // System.out.format("%4d:%-4d %d :: %d %s,\n", i, debS
                    // - i, cpt, maxTmp, sTmp);
                }

                continue;
            }

            break;
        }

        debS++;         
    }

    System.out.println("Result: " + max);

}

/** @param args */
public static void main(final String[] args) {

    singlePalindrome("abccdccba");// "abccddccba" works
    System.out.println("============================");

    // "baabcc dd ccbaabiib" works like "baabcc d ccbaabiib" (odd problem)
    final String words = "baabcc d ccbaabi o iba ab";
    palindromeNested(new StringBuilder(words).reverse().toString(), 3); // 3carsMini
    System.out.println("----------------------------");

    palindromeNested(words, maxSize / 2); // the max found in first
    System.out.println("============================");

}

}

输出 ：

单回文：abccdccba
3:c 5:c
2:c 6:c
1:b 7:b
0:a 8:a
是回文。
============================
3 =回文嵌套的最小尺寸（..）：ba abi o ibaabcc d ccbaab
5 ba ab
7 bi o ib
9 abi o iba
结果：abi o iba
----------------------------
4 = palindromeNested(..) 的最小尺寸： baabcc d ccbaabi o iba ab
11 abcc d ccba
13 aabcc d ccbaa
15 baabcc d ccbaab
结果：baabcc d ccbaab
========================== =

于 2012-07-02T08:08:07.473 回答