Problem Detail: I need to detect whether a binary pattern P of length m occurs in a binary text T of length n where m I want to state an algorithm that runs in time O(n) where we assume that arithmetic operations on O(log2n) bit numbers can be executed in constant time. The algorithm should accept with probability 1 whenever P is a substring of T and reject with probability of at least 1−1n otherwise. I think fingerprinting could help here. But I can’t get it.
Asked By : user2923183
Answered By : J.-E. Pin
The average complexity of the search from the back to the front is equal to $$ sum_{i=1}^n frac{2i}{n(n+1)}(n-i+1) = frac{2}{n(n+1)}sum_{i=1}^n i(n-i+1) = frac{2}{n(n+1)} frac{1}{6}n (n+1) (n+2) = frac{1}{3}(n+2) $$ which is indeed linear.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/16546 Ask a Question Download Related Notes/Documents
