9

解決策が存在するかどうかさえわかりません。ここに問題の詳細があります。あなたは、無限に長い文字のストリームを受け入れるプログラムです（簡単にするために、文字は1または0のいずれかであると想定できます）。いつでも、ストリームを停止して（たとえば、N文字が通過した後）、これまでに受信した文字列が回文であるかどうかを尋ねることができます。より少ない劣線形空間および/または時間を使用してこれをどのように行うことができますか。

4

4 に答える 4

6

はい。答えは、http：//rjlipton.wordpress.com/2011/01/12/stringology-the-real-string-theory/の約3分の2です。

編集：リンクが切れた場合に備えて、結果を要約するように頼まれた人もいます。リンクには、次の定理の証明に関する詳細が記載されています。最初の重要なパリンドロームをリアルタイムで認識できるマルチテープチューリングマシンがあります。 （要約、リンクされた記事によっても提供されます：マシンが入力のx1、x2、...、xkを読み取ったと仮定します。その後、x1、x2、...、xkが回文であるかどうかを判断する時間は一定です。 。）

マルチテープチューリングマシンは、読み取りと書き込みが可能な複数のテープを並べたものです。非常に具体的な意味では、標準のチューリングマシンとまったく同じです。

リアルタイム計算とは、チューリングマシンがMステップごとに少なくとも1回は入力から文字を読み取る必要がある計算です（ある制限付き定数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

明らかに、何か、おそらく素数または 2 の累乗を法としてハッシュを計算する必要があります。そしてもちろん、これは誤検知につながる可能性があります。

于 2011-02-11T00:41:39.447 に答える
0

ラウンド2

私が見ているように、新しいキャラクターごとに、次の 3 つのケースがあります。

  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」が

この3つのケースで、すべてのベースが網羅されていると思います。現在の文字列が回文かどうかを確認したい場合は、最初のポインター (プラトーのエッジ ポインターではない) がインデックス 0 にあるかどうかを確認します。

于 2011-02-11T06:44:20.290 に答える