Searching All Seeds of Strings with Hamming Distance using Finite Automata.
Saved in:
| Title: | Searching All Seeds of Strings with Hamming Distance using Finite Automata. |
|---|---|
| Authors: | Guth, Ondřej1 gutho1@fel.cvut.cz, Melichar, Bořivoj1 melichar@fel.cvut.cz |
| Source: | International MultiConference of Engineers & Computer Scientists 2009. 2009, p622-629. 8p. 5 Diagrams, 1 Chart, 3 Graphs. |
| Subjects: | Sequential machine theory, Spacetime, Approximation theory, Machine theory, Algorithms |
| Abstract: | Seed is a type of a regularity of strings. A restricted approximate seed w of string T is a factor of T such that w covers a superstring of T under some distance rule. In this paper, the problem of all restricted seeds with the smallest Hamming distance is studied and a polynomial time and space algorithm for solving the problem is presented. It searches for all restricted approximate seeds of a string with given limited approximation using Hamming distance and it computes the smallest distance for each found seed. The solution is based on a finite (suffix) automata approach that provides a straightforward way to design algorithms to many problems in stringology. Therefore, it is shown that the set of problems solvable using finite automata includes the one studied in this paper. [ABSTRACT FROM AUTHOR] |
| Copyright of International MultiConference of Engineers & Computer Scientists 2009 is the property of International Association of Engineers (IAENG) and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
Be the first to leave a comment!
