子串

一个字符串 ${\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）.