给定一个长度为S的字符串(仅假设为英文字符) n,我们可以使用以下算法计算回文子字符串的数量: p1 = number of palindromes centered我对在O(n)中解决这个问题的算法感兴趣。我确信,就像我听过很多人说的那样,确实存在这样的问题,而且这个问题存在于一个在1 000 000 on n上有上限的本地在线评判网站上,然而,我从未见过这个算法,而且似乎无法想出它。更新:
我的一般想法是为等长
我正在学习Manacher的算法来解决最长的回文子串问题,我知道它利用了这样一个事实,如果i‘是回文的中心,那么将有一个回文以i为中心。我们不是从零开始扩展,而是维护一个数组P,以跟踪回文中心在i处的len。我的问题是,如果镜像上的回文更小,我们如何知道会有大小为R-i的回文? 这是它的代码。maxLen)//2] 我找到的所有例子都是这样的 a # b # a # b # b