This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
|
||||||||
|
Paper Details
Paper Title
Text matching of strings in terms of straight line program by compressed aleshin type automata
Authors
A.Jeyanthi, B.Stalin
Abstract
In this paper we are checking the equivalence of any given text of strings is represented by a straight line program (SLP) with model text. For a given SLP-compressed Aleshin type automata D of size n and height h representing m patterns of total length N, we present an O (n2 log N)-size representation of Aho-Corasick automaton which recognizes all occurrences of the patterns in D in amortized O (h + m) running time per character. We also propose an algorithm to construct this compressed Aho-Corasick automaton in O (n3 logn log N) time and O (n2 log N) space. In a special case where D represents only a single pattern, we present an O (n log N)-size representation of the Morris-Pratt automaton which permits us to find all occurrences of the pattern in amortized O (h) running time per character, and to construct this representation in O (n3 logn log N) time with O (n2 log N) working space.
Keywords- Aho-Corasick automata, straight line program, Morris-Pratt automaton, Aleshin Type Automata
Publication Details
Unique Identification Number - IJEDR1504074Page Number(s) - 466-472Pubished in - Volume 3 | Issue 4 | November 2015DOI (Digital Object Identifier) - Publisher - IJEDR (ISSN - 2321-9939)
Cite this Article
A.Jeyanthi, B.Stalin, "Text matching of strings in terms of straight line program by compressed aleshin type automata", International Journal of Engineering Development and Research (IJEDR), ISSN:2321-9939, Volume.3, Issue 4, pp.466-472, November 2015, Available at :http://www.ijedr.org/papers/IJEDR1504074.pdf
Article Preview
|
|
||||||
|
|
||||||||
