查看“︁子串”︁的源代码

一个[[字符串]] <math>s</math> 被称作另一个字符串 <math>S</math> 的'''子串'''，表示 <math>s</math> 在 <math>S</math> 中出现了。比如，“中出”是“我们中出了一个叛徒”的子串。注意子串和[[子序列]]是不同的：“果机”是“蘋果手机”的子序列，而不是子串。

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

例如，“苹果手机”的所有子串是：“”（空串），“苹”，“果”，“手”，“机”，“苹果”，“果手”，“手机”，“苹果手”，“果手机”，“苹果手机”。

== 定义 ==

一个字符串 <math>s</math> 被称作另一个字符串 <math>S</math> 的'''子串'''，表示 <math>S=XsY</math>。

一个字符串 <math>s</math> 被称作另一个字符串 <math>S</math> 的'''前缀'''，表示 <math>S=sY</math>。

一个字符串 <math>s</math> 被称作另一个字符串 <math>S</math> 的'''后缀'''，表示 <math>S=Xs</math>。

== Border ==

一个字符串 <math>s</math> 被称作 <math>S</math> 的 '''Border'''，表示 <math>s</math> 既是 <math>S</math> 的前缀，又是其后缀。比如，“我不相信你”是“我不相信你不认为我不相信你”的 Border，"niconi"是"niconiconi"的 Border。<ref>{{Cite journal|title=Fast Pattern Matching in Strings|url=http://epubs.siam.org/doi/10.1137/0206024|last=Knuth|first=D.|last2=Morris|first2=Jr., J.|date=1977-06-01|journal=SIAM Journal on Computing|issue=2|doi=10.1137/0206024|volume=6|pages=323–350|issn=0097-5397|last3=Pratt|first3=V.|access-date=2018-02-28|archive-date=2021-03-08|archive-url=https://web.archive.org/web/20210308044511/https://epubs.siam.org/doi/10.1137/0206024|dead-url=no}}</ref>

== 参考文献 ==

{{Reflist}}

[[Category:字符串]]
[[Category:形式语言]]
{{語言小作品}}