[Solved]: Randomizd String Searching

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