поиск подстроки

Question

Я недавно пытался исследовать различные способы поиска по подстроке и наткнулся на следующую статью http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_algorithm. Мне было интересно, есть ли другие распространенные / эффективные алгоритмы, которые кто-нибудь может предложить /показать?

Большое спасибо

Answer 1

Самым очевидным будет Бойер-Мур или какой-нибудь другой вариант, например Бойер-Мур-Хорспул.Для некоторых ситуаций также стоит рассмотреть Кнут-Моррис-Пратт.

Answer 2

На мой взгляд, наиболее интуитивным и простым для понимания является алгоритм Робина Карпа

Вот простая реализация 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()

Answer 3

Алгоритм KMP эффективен при поиске подстроки, если текст небольшой.сложность O (n).для простоты понимания http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/