如何优化重复检查字符串前缀是否为回文的算法？

针对每次检查前缀s[0..curr]是否为回文的场景，完全可以通过预处理将总时间复杂度从O(n²)优化到O(n)，以下是两种实用方案：

方案一：前缀哈希+反向哈希对比 #

核心思路是通过预处理哈希值，让每次回文判断只需要O(1)的哈希对比。

具体实现 #

1. 构造哈希数组：

   • 计算原字符串的正向前缀哈希数组forward_hash，每个元素forward_hash[i]代表子串s[0..i]的哈希值（采用多项式哈希，比如hash = hash_prev * base + ord(char)，同时维护一个power数组存储base的幂次，方便后续计算）；
   • 将原字符串反转得到s_rev，计算其反向前缀哈希数组backward_hash，每个元素对应s_rev的前缀哈希。

2. 回文判断：
   对于每个curr，原前缀s[0..curr]是回文的等价条件是：它的哈希值等于其反转串（也就是s_rev中对应长度的后缀）的哈希值。通过预处理的power数组，可以快速计算出s_rev对应后缀的哈希值，和forward_hash[curr]对比即可。

   注：为了避免哈希冲突，可使用双哈希（同时用两组base和mod值计算哈希，只有两组哈希都相等才判定为回文）。

方案二：KMP失效函数（部分匹配表） #

利用KMP算法的部分匹配特性，构造拼接字符串后快速判断回文前缀。

具体实现 #

1. 构造拼接字符串：
   生成新字符串t = s + '#' + s[::-1]，其中#是一个不会出现在原字符串中的分隔符，避免原字符串和反转字符串的前缀后缀出现错误匹配。
2. 计算失效函数：
   计算t的KMP失效函数数组lps（最长前缀后缀匹配数组），其中lps[i]表示t[0..i]中最长的相等前缀和后缀的长度。
3. 回文判断：
   对于原字符串的每个位置curr，查看t中对应位置（即len(s) + 1 + curr）的lps值，如果该值等于curr+1，说明s[0..curr]是回文——因为这意味着原前缀和它的反转串完全匹配。

复杂度说明 #

两种方案的预处理和遍历判断的总时间复杂度都是O(n)，空间复杂度也是O(n)，完美解决了原方法重复线性检查导致的高复杂度问题。

内容的提问来源于stack exchange，提问作者Jeremy Fisher