知识卡片

普通读书笔记卡 · 3707.e.2

非样本后缀按首字与样本秩排序

理解等级:高级

DC3先递归排好起点位置模3余1或2的“样本后缀”,并用r[i]记录样本后缀T[i:]的名次。起点i模3余0的非样本后缀删去首字符后从i+1开始,恰好是样本后缀,所以两个非样本后缀可按二元组(T[i], r[i+1])比较:首字符不同时看T[i],相同时看余下后缀的已知名次。

合并样本与非样本时也只需常数项比较。设j模3余0:

  • 若样本起点i模3余1,比较(T[i], r[i+1])与(T[j], r[j+1]);
  • 若i模3余2,比较(T[i], T[i+1], r[i+2])与(T[j], T[j+1], r[j+2])。

第二种多比较一个字符,是为了让双方删去两个字符后都落到样本位置(起点模3余1或2)。每次比较都是常数时间,线性归并才成立。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      H. Sort the nonsample suffixes by comparing tuples (T[i], ri+1). In our example, we get T[15:] < T[12:] < T[9:] < T[3:] < T[6:] because (b, 6) < (i, 10) < (o, 9) < (p, 8) < (t, 12). 3. Merge the sorted sets of suffixes. From the sorted set of suffixes, determine the suffix array of T. This completes the description of a linear-time algorithm for computing suffix arrays. The following parts of this problem ask you to show that certain steps of this algorithm are correct and to

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[90000,95000))。 - 结论依据:原文章末问题32-2步骤H给出非样本后缀的二元组排序;随后题目要求按样本起点模3余1或2分别构造常数时间的跨组比较,上述两个元组是对应分支。 - 原始内容:H. Sort the nonsample suffixes by comparing tuples ( T [ i ], r i +1 ). In our example, we get T [15:] < T [12:] < T [9:] < T [3:] < T [6:] because ( b , 6) < ( i , 10) < ( o , 9) < ( p , 8) < ( t , 12). 3. Merge the sorted sets of suffixes. From the sorted set of suffixes, determine the suffix array of T . This completes the description of a linear-time algorithm for computing suffix arrays. The following parts of this problem ask you to show that certain steps of this algorithm are correct and to