Алгоритм Колусси

Асимптотики

• 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 [math]O(m)[/math] time and space complexity;
• searching phase in [math]O(n)[/math] time complexity;
• performs [math]3/2n[/math] text character comparisons in the worst case.

Ссылки

• Colussi algorithm
• Colussi.ppt