子串搜索

我最近一直试图调查各种方法来做子字符串搜索，并绊倒了下面的文章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

回答

相关问题