1772年加勒比海在线法官给出时间限制超出错误.请帮我解释为什么我的算法花了这么长时间

Question

所以我试图解决加勒比在线评判网页的问题1772 http://coj.uci.cu/24h/problem.xhtml?abb=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()来获取子字符串,我不认为这会导致问题.如果您需要该代码,请告诉我.谢谢!

Answer 1

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

例如，

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

baraabarbabartaarabcde
000100000000001000000-

然后计算该数组的累积和：

baraabarbabartaarabcde
000100000000001000000-
000111111111112222222-

通过做减法，您可以立即计算出查询范围内是否存在 2 个字符的回文。

类似地，对于三个字符平原：

baraabarbabartaarabcde  String
01001000100000010000--  Indicator
01112222333333344444--  Cumulative