サブストリングの検索

私は最近、サブストリングの検索を行うさまざまな方法を調査しようとしており、次の記事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

既にアルゴリズムについての記事を参照しています。それ自体が他のアルゴリズムを参照しているため、少なくとも部分的にあなた自身の質問に既に回答しているようです。あなたが持っている特定の条件や制約はありますか、あるいは一般的なトピックに興味がありますか？ –

私は主によく使われるアルゴリズムを探していると思います – locoboy

最も明白はボイヤー - ムーアや、ボイヤー - ムーア-Horspoolなど、いくつかの変種になります。状況によっては、Knuth-Morris-Prattも検討する価値があります。

出典

2011-04-03 17:38:15

KMP algorithimは、テキストが小さい場合は部分文字列検索で効率的です。複雑さ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

サブストリングの検索

答えて

関連する問題