9

我什至不知道是否存在解决方案。这里是详细的问题。您是一个接受无限长字符流的程序（为简单起见，您可以假设字符是 1 或 0）。在任何时候，我都可以停止流（假设在 N 个字符通过之后）并询问您目前收到的字符串是否是回文。您如何使用更少的次线性空间和/或时间来做到这一点。

4

4 回答 4

6

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

编辑：有些人要求我总结结果，以防链接失效。该链接提供了有关以下定理证明的一些细节：有一个多带图灵机可以实时识别初始非平凡回文。 （总结，也由链接的文章提供：假设机器已经读取了输入的x1，x2，...，xk。那么它只有恒定的时间来确定x1，x2，...，xk是否是回文.)

多磁带图灵机只是具有几个可以读取和写入的并排磁带的机器。在非常具体的意义上，它完全等同于标准的图灵机。

实时计算是图灵机必须每 M 步从输入中读取一个字符至少一次（对于某个有界常数 M）。很容易看出，任何实时算法都应该是线性时间的。

有一篇关于证明的论文大约 10 页，可在此处的机构付费墙后面找到，我不会在其他地方重新发布。如果您愿意，可以联系作者以获得更详细的说明；我最近才读到这篇文章，并意识到它或多或少是您正在寻找的。

于 2011-02-11T02:36:20.530 回答
1

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

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

显然，您必须计算哈希模数，可能是素数或二的幂。当然，这可能会导致误报。

于 2011-02-11T00:41:39.447 回答
0

第二轮

在我看来，每个新角色都有三种情况：

  1. 字符破坏了潜在的对称性，例如，aab -> aabc
  2. 字符向中间延伸，例如 aab -> aabb
  3. 字符继续对称，例如 aab->aaba

假设您有一个指针，它跟踪字符串并指向最后一个继续潜在回文的字符。

（我将使用括号来表示指向的字符）

假设您从 aa(b) 开始并得到：

  • 'a'（情况 3），将指针向左移动并检查它是否是 'a'（它是）。你现在有 a(a)b。
  • 'c'（案例 1），你不期望一个 'c'，在这种情况下，你从头开始，现在你有 aab(c)。

真正棘手的情况是 2，因为不知何故你必须知道你刚刚得到的字符并没有影响对称性，它只是延伸了中间。为此，您必须持有一个额外的指针来跟踪高原（中间）边缘所在的位置。例如，您有 (b)baabb，而您刚刚获得了另一个 'b'，在这种情况下，您必须知道将指针重置到此处的中间高原底部：bbaa(b)bb。由于我们要使用恒定时间，因此您必须先在此处握住指针（您没有时间寻找高原边缘）。现在如果你得到另一个'b'，你知道你仍然在那个高原的边缘，你把指针保持在原来的位置，所以 bbaa(b)bb -> bbaa(b)bbb。现在，如果你得到一个'a'，你就知道'b'

有了这三种情况，我认为所有的基础都涵盖了。如果您想检查当前字符串是否是回文，请检查第一个指针（不是高原的边缘指针）是否在索引 0 处。

于 2011-02-11T06:44:20.290 回答
-1

这可能会对您有所帮助： http: //arxiv.org/pdf/1308.3466v1.pdf

如果您存储最后 $k$ 个输入符号，您可以轻松找到长度为 $k$ 的回文。
如果您使用本文的算法，您可以找到回文的中点及其长度的长度估计。

于 2013-08-17T20:40:45.073 回答