ivplay's blog

need some KMP + DP related problems
By ivplay, 9 years ago, In English

Please suggest some practice problem for me that needs KMP + DP . I means such problem where the DP states depend on KMP failure function. Thanks in advance.

Tags dp, kmp
  • Vote: I like it
  • +2
  • Vote: I do not like it

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

346B - Lucky Common Subsequence

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

    Thanks a lot for your kind help. Can you please suggest some more problems? I want to solve 4-5 problems to make my concept clear.

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

You can try this problem Unlucky Strings This problems uses Matrix exponentiation + KMP.

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

At codechef: https://www.codechef.com/tags/problems/kmp At topcoder: http://community.topcoder.com/stat?c=problem_statement&pm=6017&rd=8083 and also -
MagicWords (SRM 433 D1-250/D2-500) RequiredSubstrings (SRM 519 D1-600) DengklekMessage (SRM 526 D1-1000) FoxAndMountain (SRM 557 D2-1000) At SPOJ: PRETILE, ARDA1, NHAY, PERIOD, EPLAIN, PSTRING, FINDSR, VPALIN At UVa : UVA 11475

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

http://acm.timus.ru/problem.aspx?space=1&num=1002

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

Here you go — http://www.spoj.com/problems/PSTRING/ :)

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone suggest some material to study about the topic, I can't seem to grasp how to apply kmp+dp on a problem

→ Reply