_notpalindrome_'s blog

KMP (Knuth Morris Pratt)
By _notpalindrome_, history, 6 years ago, In English

Recently I have learned KMP. I am trying to solve the problem for a while but cant understand, What should be my first approach? Can anyone explain me step by step. Any hint would be greatly appreciated.

Problem Link: http://lightoj.com/volume_showproblem.php?problem=1268 Those Who haven't any Lightoj account dont worry just visit the pdf link then you will see the problem statement. Pdf Link: http://lightoj.com/volume_showproblem.php?problem=1268&language=english&type=pdf

Sorry for my poor English. Thanks a lot.

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

»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

KMP is used to solve the subproblem: Given I matched i characters and add the character c, how many characters now match?

This is same thing as finding longest proper prefix AND suffix of S[1...i]+c which can be done with KMP idea.

Pseudocode with KMP

However, we don't need to use actual KMP algorithm, just the idea.

Pseudocode (simplified)

To finish the solution you use this data to solve the dp recurrent dp[position][matched]

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks.Can you please explain your Pseudocode though I have no idea about dp.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      If you consider base case dp[i-1][s[i]] (assuming s is one indexed) thats just i.

      Because it means i-1 have matched and now you're adding the i'th character.

      For example abradacabra

      If you are at "abra" and add a 'd' than now you are at "abrad". But if you add anything else you go back to zero. In other cases you might not go back to zero though.

      Now there are two cases for dp[i][c]

      1) dp[i][c] = dp[i][s[i+1]] = i+1

      2) dp[i][c] build off some earlier prefix

      Case one is explained above.

      In the second case adding character c to the prefix is NOT the base case. So we build off the next best thing: lps. If that doesn't work, try the next lps, and so on. Same idea behind KMP.

      Now for simplifying the implementation (you don't even need to write 'KMP' in first place!) you just have to realize at the point where you loop i that dp[i-1][s[i]] is not yet i. Instead, it is the lps. Why? Because it stores the longest matching prefix/suffix EXCLUDING the whole prefix. Which is the definition of lps.

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

in this problem apparently need to use aho korasic algorithm instead of KMP

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Both will work. As long you create a correct mismatch/failure table. I have tested the described solution on various problems and it works well (USACO, Codeforce, maybe some others)

    → Reply