5

所以我正在尝试解决加勒比在线法官网页http://coj.uci.cu/24h/problem.xhtml?abb=1772的问题 1772 ，问题要求查找较大字符串的子字符串是否包含在其中至少有一个回文：

例如，分析取自以下字符串的子字符串：“baraabarbabartaarabcde”

“bara”包含一个回文“ara”

“abar”包含一个回文“aba”

“babar”包含一个回文“babar”

“taar”包含一个回文“aa”

“abcde”不包含任何回文。

等等等等等等

我相信我的方法非常快，因为我同时从第一个字符和最后一个字符开始迭代字符串，向字符串中心前进，只寻找以下模式：“aa”“aba”每当我找到一个模式，我可以说给定的子字符串在其中包含一个回文。现在的问题是该算法需要很长时间，但我无法发现它的问题。请帮我找到它，我真的迷失了这个。这是我的算法

public static boolean hasPalindromeInside(String str)
{
    int midpoint=(int) Math.ceil((float)str.length()/2.0);
    int k = str.length()-1;

    for(int i = 0; i < midpoint;i++)
    {
        char letterLeft = str.charAt(i);
        char secondLetterLeft=str.charAt(i+1);
        char letterRight = str.charAt(k);
        char secondLetterRight =  str.charAt(k-1);

        if((i+2)<str.length())
        {
            char thirdLetterLeft=str.charAt(i+2);
            char thirdLetterRight=str.charAt(k-2);


            if(letterLeft == thirdLetterLeft || letterRight == thirdLetterRight)
            {
                return true;
            }

        }


        if(letterLeft == secondLetterLeft || letterRight==secondLetterRight)
        {
            return true;
        }

    k--;
    }
    return false;
}
}

我已经删除了获取输入字符串和子字符串间隔的代码，我正在使用 String.substring() 来获取子字符串，我认为这不会导致问题。如果您需要该代码，请告诉我。谢谢！

4

1 回答 1

1

我认为你可以在每个查询 O(1) 时间内解决这个问题，给定 O(n) 预处理以找到所有 2 和 3 个字符回文的位置。（任何偶数平原将在中心有一个 2 个字符的平原，而任何奇数将有一个 3 个字符的平原，因此检查 2 和 3 就足够了。）

例如，

给定您的字符串 baraabarbabartaarabcde，首先计算一个数组，指示 2 个字符回文的位置：

baraabarbabartaarabcde
000100000000001000000-

然后计算这个数组的累积和：

baraabarbabartaarabcde
000100000000001000000-
000111111111112222222-

通过减法，您可以立即计算出查询范围内是否有任何 2 个字符回文。

同样对于三个字符平原：

baraabarbabartaarabcde  String
01001000100000010000--  Indicator
01112222333333344444--  Cumulative
于 2013-10-06T20:08:09.127 回答