知识卡片

普通读书笔记卡 · 3704

有效位移定位模式全部出现

理解等级:初级

长度m的模式P在长度n的文本T中,位移s有效当且仅当T[s+1:s+m]=P[1:m],其中0≤s≤n−m。

字符串匹配要找出所有有效位移,不能找到第一次就结束;位移s对应文本起点s+1。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第32章 字符串匹配 · 查看原书依据

      As Figure 32.1 shows, pattern P occurs with shift s in text T (or, equivalently, that pattern P occurs beginning at position s + 1 in text T) if 0 ≤ s ≤ n – m and T[s + 1:s + m] = P[1:m], that is, if T[s + j] = P[j], for 1 ≤ j ≤ m. If P occurs with shift s in T, then s is a valid shift, and otherwise, s is an invalid shift. The string-matching problem is the problem of finding all valid shifts with which a given pattern P occurs in a given text T. Figure 32.1 An

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[0,5000))。 - 结论依据:原文定义字符串匹配、前后缀或相应算法的比较规则;相关图式已核对。 - 原始内容:As Figure 32.1 shows, pattern P occurs with shift s in text T (or, equivalently, that pattern P occurs beginning at position s + 1 in text T ) if 0 ≤ s ≤ n – m and T [ s + 1: s + m ] = P [1: m ], that is, if T [ s + j ] = P [ j ], for 1 ≤ j ≤ m . If P occurs with shift s in T , then s is a valid shift , and otherwise, s is an invalid shift . The string-matching problem is the problem of finding all valid shifts with which a given pattern P occurs in a given text T . Figure 32.1 An