找到字符串中最长的非回文子字符串

Question

我需要在字符串中找出最长的非回文子串(一个本身不是回文的字符串,无论是否有任何子串),在O(n**2)或更短的时间内.

我可以提出简单的强力算法,找到所有可能的子串(O(n**2)),然后对每个这样的子串检查是否是回文(O(n)),将整体复杂度设为O( ñ**3).

有O(n**2)变体找出最长的回文子串和序列,但我无法重复使用它们来找出解决方案.

我如何在O(n**2)时间内完成？

Answer 1

既然已经有了答案,那么让我把我的提示变成一个真正的答案:

首先,检查完整字符串是否:

• 回文(O(n),平均O(1))
• 重复相同的字符,例如"aaaaaaaaaaaa"(在同一循环中完成).

然后:

• 如果字符串不是回文,则最长的非回文子字符串就是字符串本身
• 如果字符串是回文而不是相同字符的重复,则删除任一端将使其成为非回文,并且最长的这样的子字符串
• 如果字符串是相同字符的重复,则它没有非回文子字符串.或者,根据您对回文结构的定义,唯一的非回文子字符串是空子字符串.