Problem Detail: 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.
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.
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
