跳转到内容

子串

维基百科,自由的百科全书

一个字符串 被称作另一个字符串 子串,表示 中出现了。比如,“中出”是“我们中出了一个叛徒”的子串。注意子串和子序列是不同的:“果机”是“苹果手机”的子序列,而不是子串。

前缀后缀是两种特殊的子串:一个前缀在原串的开始位置出现,而一个后缀在原串的末端出现。

例如,“苹果手机”的所有子串是:“”(空串),“苹”,“果”,“手”,“机”,“苹果”,“果手”,“手机”,“苹果手”,“果手机”,“苹果手机”。

定义

一个字符串 被称作另一个字符串 子串,表示

一个字符串 被称作另一个字符串 前缀,表示

一个字符串 被称作另一个字符串 后缀,表示

Border

一个字符串 被称作 Border,表示 既是 的前缀,又是其后缀。比如,“我不相信你”是“我不相信你不认为我不相信你”的 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).