Недавно я пытался исследовать различные способы поиска подстрок и наткнулся на следующую статью http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_algorithm. Мне было интересно, есть ли какие-либо другие распространенные/эффективные алгоритмы, которые кто-нибудь может предложить/показать?
Спасибо большое
Наиболее очевидным будет метод Бойера-Мура или его вариант, например Бойер-Мур-Хорспул. В некоторых ситуациях также стоит рассмотреть вариант Кнута-Морриса-Пратта.
Алгоритм KMP эффективен при поиске подстроки, если текст небольшой. сложность O(n). для простоты понимания http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
На мой взгляд, самым интуитивным и простым для понимания является алгоритм Робина Карпа
Вот простая реализация 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()
