POROVNÁNÍ SKUTEČNÝCH ŘETĚZCŮ
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
Jsou-li text i vzorek skutečné řetězce znaků (symboly abecedy jsou skutečné znaky jako 'a' nebo X'0E'), pak nejefektivnější řešení spočívá v použití vestavěné funkce POS jazyka Rexx.
PRAXE
V řetězci
Text, kterým je prvních 320kB souboru
REGINA.DOC, najde
REAL_STRING_MATCHER všechny výskyty vzorku
Regina za 0.1 sekundy.
KMP_MATCHER dokáže totéž za 406 sekund a
BOYER_MOORE_MATCHER za 89 sekund.
IMPLEMENTACE
Jednotka: vnitřní podprogram
Parametry: řetězec Text, řetězec Pattern
Výstup: Pro všechna nalezená posunutí zobrazí Vzorek se nachází s posunutím S
REAL_STRING_MATCHER: parse arg Text, Pattern
do F = 0 until F = 0
F = POS(Pattern, Text, F + 1)
if F > 0 then
say "Vzorek se nachází s posunutím" F - 1
end
return
|
SOUVISLOSTI
