部分文字列

形式言語理論やコンピュータサイエンスにおいて、部分文字列とは文字列内の連続した文字の並びのことです。例えば、「the best of 」は「 It was the best of times 」の部分文字列です。一方、「Itwastimes 」は「 It was the best of times 」の部分列ではありますが、部分文字列ではありません。

接頭辞と接尾辞は部分文字列の特殊なケースです。文字列の接頭辞${\displaystyle S}$は、${\displaystyle S}$最初に起こる${\displaystyle S}$同様に、文字列の接尾辞${\displaystyle S}$は、末尾に現れる部分文字列です。${\displaystyle S}$。

文字列「apple」の部分文字列は次のようになります。「a」、「ap」、「app」、「appl」、「apple」、「p」、「pp」、 「 ppl」 、「 pple」、「pl」、「ple」、「l」、「le」、「e」、「」（末尾の空文字列に注意してください）。

紐${\displaystyle u}$文字列の部分文字列（または因子）^{[ 1 ]}${\displaystyle t}$2つの文字列が存在する場合${\displaystyle p}$そして${\displaystyle s}$そのため${\displaystyle t=pus}$特に、空文字列はすべての文字列の部分文字列である。

例: 文字列${\displaystyle u={\texttt {ana}}}$は、 の部分文字列（および部分列）に等しい。${\displaystyle t={\texttt {バナナ}}}$2つの異なるオフセットで：

バナナ ||||| アナ|| ||| アナ

最初の出現は以下で得られます${\displaystyle p={\texttt {b}}}$そして${\displaystyle s={\texttt {na}}}$2回目の出現は、 ${\displaystyle p={\texttt {ban}}}$そして${\displaystyle s}$空文字列である。

文字列の部分文字列は、文字列の接尾辞の接頭辞であり、同様に接頭辞の接尾辞でもあります。たとえば、はの接頭辞であり、はの接尾辞です。nannanabanana${\displaystyle u}$は、${\displaystyle t}$また、それは部分列でもあり、これはより一般的な概念です。特定の文字列内の特定のパターンの出現は、文字列検索アルゴリズムで見つけることができます。2つ以上の文字列の部分文字列と等しい最長の文字列を見つけることは、最長共通部分文字列問題として知られています。数学文献では、部分文字列はサブワード（アメリカ）またはファクター（ヨーロッパ）とも呼ばれます。

紐${\displaystyle p}$文字列の接頭辞^{[ 1 ]です}${\displaystyle t}$文字列が存在する場合${\displaystyle s}$そのため${\displaystyle t=ps}$文字列の適切な接頭辞は、文字列自体とは等しくありません。^{[ 2 ]}一部の情報源^{[ 3 ]}では、適切な接頭辞は空でないという制約も加えています。接頭辞は、部分文字列の特殊なケースと見なすことができます。

例：文字列はban、文字列の接頭辞（および部分文字列と部分列）に等しいbanana。

バナナ ||| 禁止

正方形のサブセット記号は、接頭辞を示すために使用されることがあります。${\displaystyle p\sqsubseteq t}$は、${\displaystyle p}$は接頭辞です${\displaystyle t}$これは文字列上の二項関係を定義し、これは接頭辞関係と呼ばれ、特定の種類の接頭辞順序です。

紐${\displaystyle s}$文字列の接尾辞^{[ 1 ]です}${\displaystyle t}$文字列が存在する場合${\displaystyle p}$そのため${\displaystyle t=ps}$文字列の適切な接尾辞は、文字列自体とは等しくありません。より限定的な解釈では、空文字列でもないとされます。接尾辞は、部分文字列の特殊なケースと見なすことができる。

例：文字列はnana、文字列の接尾辞（および部分文字列と部分列）に等しいbanana。

バナナ |||| ナナ

文字列の接尾辞木は、その文字列のすべての接尾辞を表すトライ木データ構造です。接尾辞木は、文字列アルゴリズムにおいて数多くの応用例があります。接尾辞配列は、このデータ構造を簡略化したもので、接尾辞の開始位置をアルファベット順に並べたものです。接尾辞配列も同様の多くの応用例があります。

境界線は、同じ文字列の接尾辞と接頭辞です。例:${\displaystyle {\texttt {bab}}}$「は、の境界です」${\displaystyle {\texttt {ババブ}}}$「（そしてまた「$ヒヒがケバブを食べている$「」）。

有限集合のスーパーストリング${\displaystyle P}$文字列の は、すべての文字列を含む単一の文字列です。${\displaystyle P}$部分文字列として。例えば、${\displaystyle {\texttt {bcclabccefab}}}$はスーパーストリングです${\displaystyle P=\{{\texttt {abcc}},{\texttt {efab}},{\texttt {bccla}}\}}$、 そして${\displaystyle {\texttt {efabccla}}}$はより短いものです。すべてのメンバーを連結します${\displaystyle P}$任意の順序で、常に自明なスーパーストリングが得られます。${\displaystyle P}$長さが可能な限り短い超弦を見つけることは、より興味深い問題である。

指定された文字セットのすべての可能な順列を含む文字列は、スーパー順列と呼ばれます。

• 部分文字列インデックス
• 接尾辞オートマトン