子串

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

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

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

定義

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

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

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

Border

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

參考文獻

1. Knuth, D.; Morris, Jr., J.; Pratt, V. Fast Pattern Matching in Strings. SIAM Journal on Computing. 1977-06-01, 6 (2): 323–350 [2018-02-28]. ISSN 0097-5397. doi:10.1137/0206024. （原始內容存檔於2021-03-08）.