Indexing permutations for binary strings

Given a pattern P of length m and a text T of length n, 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. It is an open question whether there exists an index data structure for this problem with o(n2) time and space complexity even for a binary alphabet. In this paper, we settle this question by reducing the problem to the convolution problem and thereby achieving an time data structure for a binary string capable of answering permutation queries in O(m) time. The space requirement of the data structure is also improved to be linear.