如何检测第一次发生回文

Question

假设您正在读取字符流,则在您第一次出现回文时,该函数应该返回.

回文的长度应为偶数.

时间复杂度的要求是O(N).

例:

• 第一个字符:4
• 第二个字符:1
• 第3个字符:3
• 第四个字符:3
• 第五个字符:1
• 第6个字符:4,返回

Answer 1

在大多数情况下，应该在线性时间 O(n) 内运行的一种近似解决方案是使用滚动哈希。

您可以跟踪字符串的哈希值及其反向哈希值。每次读取一个新字符时，您都可以在 O(1) 时间内更新两个哈希值。然后比较两个哈希值，如果它们相等，则比较字符串及其保留值。如果这也相等，则退出并且您得到一个回文。

例如，一个非常简单的滚动哈希函数是 hash(ck c(k-1).. c0) = (p^k*ck + p^(k - 1) * c(k - 1) + ... + c0 ) mod m 其中 p 是奇素数。

所以从以下开始：

p = 17 // or your lucky prime number
m = 10^9 // ...
hash = 0
hash_rev = 0
str = ''
str_rev = ''
p_pow = 1    

while True
    read c
    append c to str
    prepend c to str_rev
    hash = (hash * p + c) mod m
    hash_rev = (hash_rev + p_pow * c) mod m
    p_pow = p_pow * p
    if hash == hash_rev
         if str == str_rev
             found str to be the first palindrome

为了使其更快，您可以将 hash 和 hash_rev 声明为 32 位整数并选择 m = 2^32。那么你可以忽略(mod m)操作。