Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

saurabhs1206's blog

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

I have been trying to solve the problem CPATTERN from SPOJ. Link:

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.

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