Computation of Border Array with k Substitutions in Parallel

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F06%3A03118214" target="_blank" >RIV/68407700:21230/06:03118214 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Computation of Border Array with k Substitutions in Parallel
Original language description
We present an algorithm to compute border arrray, which is used for computation of the fail function of a well known Morris-Pratt algorithm for pattern matching. Since the day of presentation of the algorithm many variations has been invented, even somefor approximate pattern-matching. Our algorithm can be used to compute border array using Hamming distance with at most k substitutions and the algorithm can be processed in parallel using O(n^2/log n) processors in O(log n) parallel time on EREW PRAM.
Czech name
Výpočet pole hranic s k substitucemi paralelně
Czech description
Přinášíme algoritmus pro výpočet border array, používané pro výpočet fail funkce dobře známého Morris-Prattovu algoritmu pro vyhledávání v textu. Od doby první preznetace tohoto algoritmu bylo objeveno mnoho variací několik dokonce pro přibližné vyhledávání. Náš algoritmus může být využit pro přibližné border array používající Hammingovy vzdálenosti a algoritmus může být vypočten paralelně na O(n^2/log n) procesorech v čase O(log n) na EREW PRAM stroji.

Project
<a href="/en/project/GA201%2F06%2F1039" target="_blank" >GA201/06/1039: Text processing and analysis</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)