文字列とは
文字の集合をアルファベットという．アルファベット $\mathit{\Sigma}$ 上の文字列とは $\mathit{\Sigma}$ 中の文字を $0$ 個以上並べた列のことである．長さ $0$ の文字列は空文字列 $\mathit{\varepsilon}$ という．
例えば， $\mathit{\Sigma=\{a,b\}}$ 上の文字列は
$\mathit{\varepsilon}$，
$a$，
$ab$，
$baabb$
などである．
アルファベット $\mathit{\Sigma}$ 上の長さ $\mathit{k}$ の文字列全体の集合を $\mathit{\Sigma}^k$ と表現し，アルファベット $\mathit{\Sigma}$ 上の文字列全体の集合を
$\mathit{\Sigma^*}$ と表現する．
例えば， $\mathit{\Sigma=\{a,b\}}$ のとき，
$\mathit{\Sigma}^0=\{\mathit{\varepsilon}\}$，
$\mathit{\Sigma}^1=\{\mathit{a,b}\}$，
$\mathit{\Sigma}^2=\{\mathit{aa,ab,ba,bb}\}$，
$\mathit{\Sigma}^*=\{\mathit{\varepsilon,a,b,aa,ab,ba,bb,aaa,aab,\ldots}\}$
である．
部分文字列・接頭辞・接尾辞
$\mathit{|S|}$ を $\mathit{S}$ の長さ，$\mathit{S}[\mathit{i}]$ を $\mathit{S}$ の$\ \mathit{i}$ $(\mathit{i}\in[1,\mathit{|S|}])$ 番目の文字とする．
文字列 $\mathit{S=S}[1]\mathit{S}[2]\ldots \mathit{S}[\mathit{|S|}]$ の部分文字列$\ \mathit{S}[\mathit{l,r}]$ とは，文字列 $\mathit{S}$ 中に出現する開始位置が $\mathit{l}$ で，終了位置が $\mathit{r}$ である文字列 $\mathit{S}[\mathit{l}]\mathit{S}[\mathit{l}+1]\ldots \mathit{S}[\mathit{r}](1\leq \mathit{l}\leq \mathit{r}\leq \mathit{|S|})$ のことである．
ただし，$\mathit{\varepsilon}$ も文字列 $\mathit{S}$ の部分文字列である．
例えば， $\mathit{S=abaab}$ のとき
その部分文字列は
$\mathit{\varepsilon,a,ab,baa,aa,aab,abaab}$
などである．
接頭辞と接尾辞は特殊な部分文字列である．
文字列 $\mathit{S}$ の接頭辞とは開始位置が $1$ の $\mathit{S}$ の部分文字列 $\mathit{S}[1,\mathit{r}](1\leq \mathit{r} \leq \mathit{|S|})$ である．
ただし，$\mathit{\varepsilon}$ も文字列 $\mathit{S}$ の接頭辞である．
例えば，$\mathit{S=abaab}$ のとき，
接頭辞は
$\mathit{\varepsilon,a,ab,aba,abaa,abaab}$
である．
文字列 $\mathit{S}$ の接尾辞とは終了位置が $\mathit{|S|}$ の $\mathit{S}$ の部分文字列
$\mathit{S}[\mathit{l},\mathit{|S|}](1\leq \mathit{l} \leq \mathit{|S|})$ である．
ただし，$\mathit{\varepsilon}$ も文字列 $\mathit{S}$ の接尾辞である．
例えば，$\mathit{S=abaab}$ のとき，
接尾辞は
$\mathit{abaab,baab,aab,ab,b,\varepsilon}$
である．