子串
一個字符串 被稱作另一個字符串 的子串,表示 在 中出現了。比如,「中出」是「我們中出了一個叛徒」的子串。注意子串和子序列是不同的:「果機」是「蘋果手機」的子序列,而不是子串。
前綴和後綴是兩種特殊的子串:一個前綴在原串的開始位置出現,而一個後綴在原串的末端出現。
例如,「蘋果手機」的所有子串是:「」(空串),「苹」,「果」,「手」,「機」,「蘋果」,「果手」,「手機」,「蘋果手」,「果手機」,「蘋果手機」。
定義
一個字符串 被稱作另一個字符串 的子串,表示 。
一個字符串 被稱作另一個字符串 的前綴,表示 。
一個字符串 被稱作另一個字符串 的後綴,表示 。
Border
一個字符串 被稱作 的 Border,表示 既是 的前綴,又是其後綴。比如,「我不相信你」是「我不相信你不認為我不相信你」的 Border,"niconi"是"niconiconi"的 Border。[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).
![]() | 這是一篇語言小作品。您可以透過編輯或修訂擴充其內容。 |