子串搜索

我最近一直試圖調查各種方法來做子字符串搜索，並絆倒了下面的文章http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_algorithm。我想知道是否有任何其他常見/有效的算法，任何人都可以建議/顯示？子串搜索

感謝很多

來源

2011-04-03 locoboy

你看看[字符串搜索算法]（http://en.wikipedia.org/wiki/String_searching_algorithm）？ – Gumbo 2011-04-03 16:48:32

您已經參考了一篇有關算法的文章，該文章本身引用了其他算法，因此您似乎已經至少部分地回答了您自己的問題。您是否有任何特定的條件或限制，或者您是否對這個主題感興趣？ – 2011-04-03 17:53:10

我想我主要是在尋找常用的算法 – locoboy 2011-04-04 18:13:25

最明顯的是博耶 - 穆爾或其變型，如博耶 - 穆爾 - Horspool。在某些情況下，也值得考慮Knuth-Morris-Pratt。

來源

2011-04-03 17:38:15

如果文本很小，KMP算法在子字符串搜索中很有效。 O（n）。爲便於理解 http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/

來源

2015-03-15 19:48:04

在我看來是迄今爲止最intuitave和易於理解的是Robin Karp Algorithm

下面是一個簡單的Python實現

def computeHash(p): 
    return sum ([ value*10**index for (index,value) in enumerate(p[::-1]) ]) 

def getPosition(string,subString): 
    kh=computeHash(subString) 
    lk=len(subString) 
    ans=[] 
    for i in enumerate(string): 
     if len(string[i[0]:i[0]+lk])<lk: 
      break 
     else: 
      if computeHash(string[i[0]:i[0]+lk])==kh: 
       ans.append((i[0],i[0]+lk)) 
    return ans 

def main(): 

    s="hello world" #string 
    ss="wor" #sub string 

    print getPosition(map(ord,s),map(ord,ss)) 



if __name__=="__main__": 
    main()

來源

2016-12-01 13:31:37 NinjaGaiden

回答

相關問題