A linear-time algorithm for finding approximate shortest common superstrings |
| |
Authors: | Esko Ukkonen |
| |
Affiliation: | (1) Department of Computer Science, University of Helsinki, Teollisuuskatu 23, SF-00510 Helsinki, Finland |
| |
Abstract: | Approximate shortest common superstrings for a given setR of strings can be constructed by applying the greedy heuristics for finding a longest Hamiltonian path in the weighted graph that represents the pairwise overlaps between the strings inR. We develop an efficient implementation of this idea using a modified Aho-Corasick string-matching automaton. The resulting common superstring algorithm runs in timeO(n) or in timeO(n min(logm, log¦¦)) depending on whether or not the goto transitions of the Aho-Corasick automaton can be implemented by direct indexing over the alphabet . Heren is the total length of the strings inR andm is the number of such strings. The best previously known method requires timeO(n logm) orO(n logn) depending on the availability of direct indexing.This work was supported by the Academy of Finland. |
| |
Keywords: | Shortest common superstring Approximation algorithm Linear-time algorithm Greedy heuristics Hamiltonian path |
本文献已被 SpringerLink 等数据库收录! |