子串

一個字符串 $s$ 被稱作另一個字符串 $S$ 的子串，表示 $s$ 在 $S$ 中出現了。比如，「中出」是「我們中出了一個叛徒」的子串。注意子串和子序列是不同的：「果機」是「蘋果手機」的子序列，而不是子串。

前綴和後綴是兩種特殊的子串：一個前綴在原串的開始位置出現，而一個後綴在原串的末端出現。

例如，「蘋果手機」的所有子串是：「」（空串），「苹」，「果」，「手」，「機」，「蘋果」，「果手」，「手機」，「蘋果手」，「果手機」，「蘋果手機」。

定義

一個字符串 $s$ 被稱作另一個字符串 $S$ 的子串，表示 $S=XsY$。

一個字符串 $s$ 被稱作另一個字符串 $S$ 的前綴，表示 $S=sY$。

一個字符串 $s$ 被稱作另一個字符串 $S$ 的後綴，表示 $S=Xs$。

Border

一個字符串 $s$ 被稱作 $S$ 的 Border，表示 $s$ 既是 $S$ 的前綴，又是其後綴。比如，「我不相信你」是「我不相信你不認為我不相信你」的 Border，"niconi"是"niconiconi"的 Border。