算法导论笔记0x16 —— 子串搜索

KMP

m is the length of text
n is the length of pattern

  • [Prefix Array Logic]
  • 初始j指向0索引,i指向1索引
  • 数组0索引初始化为0
  • 检查匹配
    • 不匹配时,跳到j索引的前一个数组值所对应的索引位置继续检查匹配
      • 不匹配时,j=Array[j-1]
      • 若j是0,数组值为0,Array[i]=0
    • 匹配时,数组中的值为j的值加1,i和j同时加1继续检查匹配
      • Array[i]=j+1, i++, j++

Rabin-Karp Algorithm

  • Choose a prime number. Here we chose 3.
    • prime = 3
  • Value of a char:
    • a → 1, b → 2, c → 3,  …, z → 26
  • Hash of a string:
    • abe → 1 + 2 × 31 + 5 × 32 = 52
    • bed → 2 + 5 × 31 + 4 × 32 = (hash(abe)−1)+4 × 32 = 53
    • Conclude to three steps:
      1. x = oldhash − val(oldchar)
      2. x = x/prime
      3. newhash = x + primem − 1 × val(newchar)

Materials

Leave a Reply

Your email address will not be published.