# Product Matching problem in pattern matching

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