部分文字列

形式言語理論とコンピュータサイエンスでは、部分文字列は文字列内の連続した文字のシーケンスです。^[要出典]たとえば、「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 」、「」となります（末尾の空文字列に注意してください）。

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

例: 文字列は、 2 つの異なるオフセットにある の部分文字列 (および部分シーケンス) と等しくなります。 ${\displaystyle u=}$ana${\displaystyle t=}$banana

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

最初の出現はおよびを使用して取得され、2 番目の出現は およびが空の文字列で取得されます。 ${\displaystyle p=}$b${\displaystyle s=}$na${\displaystyle p=}$ban${\displaystyle s}$

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

文字列が存在する場合、その文字列は文字列の接頭辞^[1]である。文字列の適切な接頭辞は文字列自体と同じではない。^[2]一部の情報源^[3]では、さらに適切な接頭辞が空でないことを制限している。接頭辞は部分文字列の特殊なケースとみなすことができる。 ${\displaystyle p}$${\displaystyle t}$${\displaystyle s}$${\displaystyle t=ps}$

例: 文字列はban文字列のプレフィックス (および部分文字列と部分シーケンス) と等しくなりますbanana。

バナナ
|||
禁止

正方形部分集合の記号は接頭辞を示すために使用される場合があり、 はがの接頭辞であることを示します。これは、接頭辞関係と呼ばれる文字列上の2 項関係を定義します。これは、特別な種類の接頭辞順序です。 ${\displaystyle p\sqsubseteq t}$${\displaystyle p}$${\displaystyle t}$

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

例: 文字列はnana文字列の接尾辞 (および部分文字列と部分シーケンス) と等しくなりますbanana。

バナナ
  ||||
  ナナ

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

境界線は同じ文字列の接尾辞と接頭辞です。たとえば、「bab」は「babab」の境界線です (また、「ケバブを食べているヒヒ」の境界線でもあります)。^{[引用が必要]}

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

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

• 括弧記法
• 部分文字列インデックス
• サフィックスオートマトン