知识卡片
前缀与后缀包含空串和整串
若x=wy,则w是x的前缀;若x=yw,则w是x的后缀。
空串及x本身都可算前后缀,只有长度严格小于x时才称真前缀或真后缀;这些定义给后续匹配失败后的重用关系提供语言。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第32章 字符串匹配 · 查看原书依据
A string w is a prefix of a string x, denoted w ⊏ x, if x = wy for some string y ∈ ∑*. Note that if w ⊏ x, then |w| ≤ |x|. Similarly, a string w is a suffix of a string x, denoted w ⊐ x, if x = yw
参考来源
- 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[4530,5050))。
- 结论依据:原文定义字符串匹配、前后缀或相应算法的比较规则;相关图式已核对。
- 原始内容:A string w is a prefix of a string x , denoted w ⊏ x , if x = wy for some string y ∈ ∑*. Note that if w ⊏ x , then | w | ≤ | x |. Similarly, a string w is a suffix of a string x , denoted w ⊐ x , if x = yw
- 补充摘录:for a proper suffix . The empty string ϵ is both a suffix and a prefix of every string. For any strings x and y and any character