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


Obálka Obsah Index Hlavní stránka

změněno 28. září 2001
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.