saurabhs1206's blog

By saurabhs1206, history, 2 months ago, In English,

I have been trying to solve the problem CPATTERN from SPOJ. Link: https://www.spoj.com/problems/CPATTERN/.

I store the input sequence in text[] and subgroup sequence in pattern[]. Using text[], I created another array diffText[] that stores:

diffText[i] = 1 if text[i - 1] > text[i],
diffText[i] = 0 if text[i - 1] == text[i],
diffText[i] = -1 if text[i - 1] < text[i]

In the same way, I construct the array diffPattern[] for pattern[]. Then I use KMP to search for the diffPattern[] in diffText[]. It shows wrong answer. Is this incorrect approach? Please help.

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it