The Product Matching problem is defined as follows:
Input: Text T=t0,...,tn and pattern P=p0,...,pm over alphabet Σ=N .

Output : All of the i places in the text where exists ci which holds ti+j = ci * pj 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 ci=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.


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.