Daily Archives: December 2, 2021

string search算法整理 (Knuth–Morris–Pratt algorithm)

這邊列出一個字串算法Knuth–Morris–Pratt algorithm的一個實現,這邊使用的failure function value指最長prefix的最後一個字元的index,-1代表 no prefix match 字串的算法看起來很短,但是對於初學者來說非常不容易記憶或理解,主要的原因是死記一定容易忘記,並且failure function value有不同版本的詮釋,如果死記可能會看到不同版本的解法而混亂記憶,理解其中的核心概念非常重要 整個KMP算法的核心思想可以簡單用一句話描述: 比對target string suffix = pattern string prefix,比失敗則退而求其次(再找target string suffix = 次短的pattern string prefix) 在下面的說明中,I代表target string index to compare,J代表pattern string index to compare KMP的算法可參考 https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm 原始的字串搜尋算法就是很直觀的將pattern和target一一比對,但是這樣一來worse case就是 O(n * m),例如 … Continue reading

Posted in Algorithm | Leave a comment