如何从子线性空间/时间中的字符流计算回文？

Question

我甚至不知道是否存在解决方案.这是问题的细节.您是一个接受无限长字符流的程序(为简单起见,您可以假设字符为1或0).在任何时候,我都可以停止流(让我们说N个字符通过后)并询问你到目前为止收到的字符串是否是回文.如何使用较少的线性空间和/或时间来做到这一点.

Answer 1

是.答案是大约三分之二的下降http://rjlipton.wordpress.com/2011/01/12/stringology-the-real-string-theory/

编辑:有些人要求我总结结果,以防链接死亡.该链接提供了有关以下定理的证明的一些细节:有一个多磁带图灵机可以实时识别初始非平凡的回文. (摘要,链接文章也提供:假设机器读取了输入的x1,x2,...,xk.那么它只有恒定的时间来决定x1,x2,...,xk是否为回文.)

多点图灵机只是一个带有几个可以读写的并排磁带的机器; 在非常具体的意义上,它完全等同于标准的图灵机.

实时计算是指图灵机必须每M步至少一次从输入读取一个字符(对于某些有界常数M).很容易看出,任何实时算法都应该是线性时间.

有一份关于证据的论文大约有10页,可以在机构付费墙后面找到,我不会在其他地方转发.如果您愿意,可以联系作者以获得更详细的解释; 我刚刚读过这篇文章并意识到它或多或少是你想要的.

Answer 2

您可以使用滚动哈希或更多滚动哈希来提高准确性。按照读取的顺序以及读取的相反顺序增量计算到目前为止读取的字符的哈希值。

x*3^(k-1)+x*3^(k-2)+...+x*3^0例如，如果您的哈希函数x是您读取的字符在哪里，那么您将这样做：

hLeftRight = 0
hRightLeft = 0
k = 0

repeat until there are numbers in the stream
    x = stream.Get()    

    hLeftRight = 3*hLeftRight + x.Value
    hRightLeft = hRightLeft + 3^k*x.Value

    if (x.QueryPalindrome = true)
        yield hLeftRight == hRightLeft

    k = k + 1

显然，您必须以某个值（可能是素数或 2 的幂）为模来计算哈希值。当然，这可能会导致误报。