Алгоритм Колусси — различия между версиями
Kabanov (обсуждение | вклад) (init) |
Kabanov (обсуждение | вклад) м |
||
| Строка 2: | Строка 2: | ||
==Псевдокод== | ==Псевдокод== | ||
==Асимптотики== | ==Асимптотики== | ||
| + | * partitions the set of pattern positions into two disjoint subsets; the positions in the first set are scanned from left to right and when no mismatch occurs the positions of the second subset are scanned from right to left; | ||
| + | * preprocessing phase in <tex>O(m)</tex> time and space complexity; | ||
| + | * searching phase in <tex>O(n)</tex> time complexity; | ||
| + | * performs <tex>3/2n</tex> text character comparisons in the worst case. | ||
| + | |||
==Сравнение с другими алгоритмами== | ==Сравнение с другими алгоритмами== | ||
===Достоинства=== | ===Достоинства=== | ||
===Недостатки=== | ===Недостатки=== | ||
==Ссылки== | ==Ссылки== | ||
| + | * [http://www-igm.univ-mlv.fr/~lecroq/string/node10.html Colussi algorithm] | ||
| + | * [http://alg.csie.ncnu.edu.tw/course/StringMatching/Colussi.ppt Colussi.ppt] | ||
Версия 18:03, 14 мая 2014
Содержание
Алгоритм
Псевдокод
Асимптотики
- partitions the set of pattern positions into two disjoint subsets; the positions in the first set are scanned from left to right and when no mismatch occurs the positions of the second subset are scanned from right to left;
- preprocessing phase in time and space complexity;
- searching phase in time complexity;
- performs text character comparisons in the worst case.
