NAIVNÍ ALGORITMUS POROVNÁNÍ
PROBLÉM
Text je pole T.1,T.2,...,T.N a vzorek je pole P.1,P.2,...,P.M. Prvky P. a T. jsou znaky konečné abecedy Sigma., Sigma. je pole R prvků. Řekneme, že vzorek P. se nachází v textu T. s posunutím S, jestliže 0<=S<=N-M a T.SpJ=P.J, kde SpJ označuje S+J, pro J=1,...,M. Problém porovnání řetězců spočívá v nalezení všech těchto posunutí.
ALGORITMUS
V nejhorším případě je časová složitost naivního porovnávacího algoritmu O(N**2).
PRAXE
Jsou-li text i vzorek skutečné řetězce znaků, pak nejrychlejší řešení nabízí
REAL_STRING_MATCHER. V obecném případě tu není jednoznačný vítěz a nejlépe uděláme, když si podprogramy otestujeme na typických datech.
Uveďme si příklad, ve kterém
M označuje počet prvků
P.,
R označuje počet prvků
Sigma. a
S označuje počet objevených posunutí:
| Doba běhu v sekundách pro N = 100000 |
| Algoritmus |
M=10,R=1999,S=50 |
M=10,R=4,S=10000 |
M=100,R=4,S=10000 |
| Naivní |
16 |
25 |
150 |
| KMP |
21 |
22 |
23 |
| Boyer-Moore |
4 |
15 |
138 |
IMPLEMENTACE
Jednotka: vnitřní podprogram
Globální proměnné: pole T.1,...,T.N řetězců, pole P.1,...,P.M řetězců
Parametry: přirozené číslo N - počet prvků T., přirozené číslo M - počet prvků P.
Výstup: Pro všechna nalezená posunutí zobrazí Vzorek se nachází s posunutím S
NAIVE_STRING_MATCHER:
procedure expose T. P.
parse arg M, N
do S = 0 to N - M + 1
do J = 1 to M
SpJ = S + J
if P.J <> T.SpJ then iterate S
end
say "Vzorek se nachází s posunutím" S
end
return
|
SOUVISLOSTI
Literatura
Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms
The MIT Press, Cambridge, 1990
