Text matching of strings in terms of straight line program by compressed aleshin type automata
Aho-Corasick automata, straight line program, Morris-Pratt automaton, Aleshin Type Automata
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.
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 ISSN:2321-9939, Vol.3, Issue 4, pp.466-472, URL :https://rjwave.org/ijedr/papers/IJEDR1504074.pdf
Volume 3 Issue 4
Pages. 466-472
