知识卡片
有效位移定位模式全部出现
长度m的模式P在长度n的文本T中,位移s有效当且仅当T[s+1:s+m]=P[1:m],其中0≤s≤n−m。
字符串匹配要找出所有有效位移,不能找到第一次就结束;位移s对应文本起点s+1。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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