A String Problem
In string matching, there is a nice open problem from Gadi Landau that seems to need a chunk of combinatorics:
Input: A test string T of length n, may be preprocessed.
Query: A pattern string P of length m. Output is all locations i such that T[i,...,i+m-1] \equiv to P[1,...,m], where two strings s and t are \equiv if there is a permutation of s that equals t.
What is the closest to O(n) preprocessing and |P| query processing one can get? Notice that |P| may be smaller than m, since P can be presented as a vector of characters and their frequencies.
Input: A test string T of length n, may be preprocessed.
Query: A pattern string P of length m. Output is all locations i such that T[i,...,i+m-1] \equiv to P[1,...,m], where two strings s and t are \equiv if there is a permutation of s that equals t.
What is the closest to O(n) preprocessing and |P| query processing one can get? Notice that |P| may be smaller than m, since P can be presented as a vector of characters and their frequencies.
posted by metoo at 4:10 AM
9 Comments:
I may misunderstand the problem, but can we move a window of size |P| from left to right? For each symbol count the number of occurrences, and maintain a variable which counts the number of counters which match the number of symbols in P. Each time we move the window to the right by one character, at most three counters will be changed. No preprocessing is required and the running time will be O(n+m).
What you propose is an approach for solving the problem when text and the pattern are given together. The open problem is the indexing (or aka online) version where one wants query processing time to be o(n). You can spend ~\tilde(O)(n) time preprocessing the text once for all, but after that *each* query should be processed in time a function of |P| and something that is either independent of n, or if it can't be avoided, a mild function of n like log n.
-- metoo
After writing the comment I found what I misunderstood. :(
A simple solution would be to take the set of sorted substrings T[i,...,i+m-1] and store a hash value for each sorted substring. To look up P, you sort it, hash, and look for the hash value in the stored set. This of course assumes that m is known when constructing the data structure.
Yes, in the indexing problem, alas, m is known only at the query time.
-- metoo
Will the answer also depend on the frequency of occurrence of the string P in the string T?
Assuming finite alphabet size, one way might be to first construct the suffix array of the string T, sort them and store the locations in an array. For m=1, we can then directly look up from the array. For m=2, we can now proceed by shortlisting the two candidate suffix sets and then look at the second alphabet in these sets and so on. Though, I am not sure of the complexity of sorting of teh suffix array (the preprocessing)
The approach of progressively refining some set of candidate positions as you propose may work in practice. But it may take O(n) time or more in simple examples and it is not clear that is needed. Say T = (acb)^n, and pattern you are looking for is (ab). Both a and b have O(n) sized lists, but their adjusted intersection has none.
-- metoo
If I understand the notation correctly the string T is given by
T=acbacbacbacb.....
Since the pattern we are looking for is ab there will be O(n) occurrences of P in T as there will be O(n) occurrences of ba.
This is what I was referring to when I was wondering if the answer also depends on the frequency of occurrence of the string P in the string T?
Sorry, let T=(acbd)^n.
-- metoo
Post a Comment
<< Home