知识卡片

普通读书笔记卡 · 3704.b

前缀与后缀包含空串和整串

理解等级:初级

若x=wy,则w是x的前缀;若x=yw,则w是x的后缀。

空串及x本身都可算前后缀,只有长度严格小于x时才称真前缀或真后缀;这些定义给后续匹配失败后的重用关系提供语言。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 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