Sub-quadratic time and linear space data structures for permutation matching in binary strings

Given a pattern P of length n and a text T of length m, the permutation matching problem asks whether any permutation of P occurs in T  . Indexing a string for permutation matching seems to be quite hard in spite of the existence of a simple non-indexed solution. In this paper, we devise several o(n2)o(n2) time data structures for a binary string capable of answering permutation queries in O(m)O(m) time. In particular, we first present two O(n2/logn) time data structures and then improve the data structure construction time to O(n2/log2n). The space complexity of the data structures remains linear.