c语言求一个字符串里有几个子串?
从如何确定一个子串是否是回文串开始,我们需要知道这样的 pair(中心,半径)。意思是从每个中心点最多可以向左或者向右扩展的半径。因为回文串长度可能是奇数或偶数,可以用一种技巧来消除这种特判,在相邻字符中间插入一个特殊字符(如 ‘#’)。
例如,“12212321" => "#1#2#2#1#2#3#2#1#",如果令 P[i] 为以第 i 个字符为中心的扩展半径,你会发现其对应的最长回文串的长度就是 P[i] - 1。
S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 # P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1 (p.s. 可以看出,P[i]-1正好是原字符串中回文串的总长度)
(参考自:
O(n)时间求字符串的最长回文子串 - Felix021 - 将所有欢脱倾翻
O(n)时间求字符串的最长回文子串 - Felix021 - 将所有欢脱倾翻
)所以就归结到如何求 P 数组的问题。为了节约轮子成本,求解过程请参考上述链接。
这就是
马拉车算法
啊!
