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

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

例如,「蘋果手機」的所有子串是:「」(空串),「苹」,「果」,「手」,「機」,「蘋果」,「果手」,「手機」,「蘋果手」,「果手機」,「蘋果手機」。

定義

編輯

一個字符串   被稱作另一個字符串  子串,表示  

一個字符串   被稱作另一個字符串  前綴,表示  

一個字符串   被稱作另一個字符串  後綴,表示  

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).