最も左の最大周期性の解明

Main describes an algorithm for
detecting all ‘leftmost maximal’ periodicities in a string in
linear time, using the following definitions:

  • A periodicity of a string $x$ a nonempty substring of
    $x$ of the form $p^mq$ with $mge2$ and $q$ a proper prefix of
    $p$.
  • A leftmost periodicity of $x$ is a periodicity $x[i]
    dots x[j]$ such that if $x[i] dots x[j] = x[i’] dots x[j’]$ then
    $i le j$.
  • A periodicity $x[i] dots x[j]$ with period $k$ is
    maximal if:

    1. $i = 1$ or $x[i – 1] dots x[j]$ is not a periodicity with
      period $k$, and
    2. $j = |x|$ or $x[i] dots x[j + 1]$ is not a periodicity with
      period $k$

Mainは定理(3.4)を提示する:文字列$ x = u_1 dots u_k $のs因子分解を与え、$ r $を$ x
$の周期性とすると、$ r $が$ xで一番左に現れる$ x $の$ i ^ {th} $位置は$ u_h
$より前に発生します。

この定理は、与えられた文字列$ x $の「最左端の最大」周期性を計算するためのアルゴリズムの基礎を形成します。アルゴリズムは$
2 le h le k $の$ t_hu_h $のすべての最大周期性を求めます。$ t_h $は長さ$ 2 | u_
{h-1}の部分文字列です。 + | u_h | $は$ u_h $の直前にあり、各周期性は$ t_h $で始まり$ u_h
$で終わります。

私の質問は、特に、これが “左端最大”のどちらかである周期性、または
“最左端である最大周期性”と解釈されるべきならば、 “左端最大値”の意味に関係します。区別を明確にするために、文字列$ x =
aaabcaabd $を考えてみましょう。明らかに、$ x [1] $から始まる周期性$ aaa
$は両方の解釈の下で最大限に残っていますが、$ x [6] $から始まる周期性$ aa
$も最大です。最初の解釈によると、そうではなく、$ x $は1つの最も左の最大周期性しか持たない。第2によれば、それはであり、$ x
$は2つの最も左の最大周期性を有する。

私の考えでは、Mainのアルゴリズムは第1種の「最左端の最大」周期性を与えているようです。つまり、$ aaabcaabd
$のs因子分解は$ a | aa | b | c | aab | d $です。 $ x [6] $は完全に1つのs-因子($ u_5
= aab $)に含まれているのでインクルードされません。

しかし、私が知る限り、 KolpakovとKucherovの結果は、
a>は、線形時間内のストリングのすべての最大周期性を計算するために、第2の定義を仮定する。
KolpakovとKucherovは、アルゴリズムの主要コンポーネントとしてMainの結果を使用します。

ベストアンサー

mainは、彼のアルゴリズムが非現実的または非非常に周期的な出現を出力するかもしれないことを明示している。実際、定理3.4は、最も左の最大周期性が少なくとも1回は報告され、出力の合計サイズは入力文字列のサイズが線形であることを保証するだけです。すなわち、

  1. $ t_h u_h $の接尾辞であり、それでも右に拡張できる非最大の周期性を報告するかもしれません。
  2. 同一の部分文字列が複数存在し、単一のS-factorに収まらないものもあります。

KolpakovとKucherovは、$ t_h u_h $の接尾辞を除外して$ t_h $または$ u_h
$のいずれかを空にするようにMainのアルゴリズムを少し変更します。このようにしてアルゴリズムは非最大周期性を報告することはなく、同時にいくつかのs因子にまたがって境界に接触する最大周期性のあらゆる発生を見つける。

だから、KolpakovとKucherovは一番左の出来事という概念に全く依存していない。彼らは、厳密にs因子分解の単一因子の中にないすべての周期性を見いだすだけでよい。
(もちろん、合計で線形の出現数しかないことを証明してください)。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です