#文字列とは
文字の集合をアルファベットという.アルファベット $\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}$
である.