Parameterized DAWGs: Efficient constructions and bidirectional pattern searches

Two strings and over of equal length are said to () if there is a renaming bijection that is identity on Σ and transforms to (or vice versa). The problem is to look for substrings in a text that p-match a given pattern. In this paper, we propose () and () which are the p-matching versions of suffix automata and DAWGs. While suffix automata and DAWGs are equivalent for standard strings, we show that p-suffix automata can have nodes and edges but PDAWGs have only nodes and edges, where is the length of an input string. We also give an -time -space algorithm that builds the PDAWG in a left-to-right online manner. As a byproduct, it is shown that the for the reversed string can also be built in the same time and space, in a right-to-left online manner. This duality also leads us to two further efficient algorithms for p-matching: Given the parameterized suffix tree for the reversal of the input string , one can build the PDAWG of in time in an offline manner; One can perform p-matching in time using space, where denotes the pattern length and is the number of pattern occurrences in the text .