所以我正在尝试解决加勒比在线判断网页的问题 1772 http://coj.uci.cu/24h/problem.xhtml?abb=1772，问题要求查找较大字符串的子字符串是否包含至少一个回文：
例如，分析从以下字符串中获取的子字符串："baraabarbabartaarabcde">
">bara"包含一个回文"ara">
">abar"包含一个回文"aba">
"巴巴尔">包含一个回文"巴巴尔">
">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(( 来获取子字符串，我认为这不会导致问题。如果您需要该代码，请告诉我。 谢谢！
我认为您可以在给定 O(n( 预处理的情况下在每个查询的 O(1( 时间内解决这个问题，以查找所有 2 字符和 3 个字符回文的位置。 (任何偶数平原在中心都有一个 2 个字符的平原，而任何奇数都会有一个 3 个字符的平原，因此检查 2 和 3 就足够了。
例如
给定您的字符串baraabarbabartaarabcde，首先计算一个数组，指示2个字符回文的位置：
baraabarbabartaarabcde
000100000000001000000-
然后计算此数组的累积总和：
baraabarbabartaarabcde
000100000000001000000-
000111111111112222222-
通过做减法，您可以立即计算出查询范围内是否有任何 2 个字符的回文。
同样，对于三个字符的平原：
baraabarbabartaarabcde String
01001000100000010000-- Indicator
01112222333333344444-- Cumulative