Какие существуют алгоритмы сопоставления строк, кроме Кнута-Морриса-Пратта, Рабина-Карпа и тому подобное?

Question

Какие существуют алгоритмы сравнения строк, кроме Кнута-Морриса-Пратта, Рабина-Карпа и им подобных?

Answer 1

Хорошо процитированный сборник этих алгоритмов можно найти в:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.4896&rep=rep1&type=pdf

Включены следующие алгоритмы:

Karp-Rabin 
Shift Or 
Morris-Pratt 
Knuth-Morris-Pratt
Simon 
Colussi 
Galil-Giancarlo 
Apostolico-Crochemore
Not So Naive 
Forward Dawg Matching  
Boyer-Moore 
Turbo-BM 
Apostolico-Giancarlo 
Reverse Colussi 
Horspool 
Quick Search 
Tuned Boyer-Moore
Zhu-Takaoka 
Berry-Ravindran 
Smith 
Raita 
Reverse Factor 
Turbo Reverse Factor 
Backward Oracle Matching 

плюс еще около 15 других.

Кстати, вы можете уточнить, если вас также интересуют алгоритмы сходства строк (например, расстояние Левенштейна и т. Д.), Которые тесно связаны, если вы действительно заинтересованы в этом.

Answer 2

Simone Faro и Thierry Lecroq предоставляют реализацию C и ссылаются на 86 алгоритмов точного сопоставления строк на «Инструмент исследования алгоритмов сопоставления строк» ​​.

Они также предоставляют платформу для сравнения алгоритмов сопоставления строк:

____________________________________________________________
Experimental results on englishTexts
Searching for a set of 200 patterns with length 128
Testing 5 algorithms

 - [1/5] BM ..................[OK]      0.88 ms       
 - [2/5] EPSM ................[OK]      0.38 ms       
 - [3/5] KMP .................[OK]      6.23 ms       
 - [4/5] KR ..................[OK]      1.84 ms       
 - [5/5] TW ..................[OK]      2.70 ms       

алгоритмы

• BM = Бойер Мур (1977)
• EPSM = Точный алгоритм сопоставления упакованных строк (2013)
• KMP = Кнут Моррис-Пратт (1977)
• KR = Карп Рабин (1987)
• TW = Two Way (1991)

Answer 3

Эта страница содержит краткие описания многих алгоритмов: http://www -igm.univ-mlv.fr / ~ lecroq / string / index.html