[Solved]: Product Matching problem in pattern matching

Problem Detail: 

The Product Matching problem is defined as follows:
Input: Text T=t₀,...,t_n and pattern P=p₀,...,p_m over alphabet Σ=N .

Output : All of the i places in the text where exists c_i which holds t_i+j = c_i * p_j for every j=0,...,m

For example: T= 2,3,9,12,1,8 P = 1,3,4 so in index 1 there is a match for c_i=3 because: 1*3 = 3 , 3*3=9, 4*3=12

I've only managed to think about the naive way of multiplying the pattern for each number that gives us less or equal value to max{T} and then checking it with a regular O(N) pattern matching algorithm.

Asked By : d10795251

Answered By : Yuval Filmus

Hint: Starting with the original text, form a sequence $s_1,\ldots,s_n$ by the rule $s_i = t_i/t_{t-1}$, and similarly from the original pattern form a sequence $q_1,\ldots,q_m$ by the rule $q_j = p_j/p_{j-1}$. Look for the pattern $q$ inside the text $s$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47278

 Ask a Question

 Download Related Notes/Documents