brdy's blog

By brdy, history, 15 months ago, In English,

There is a problem that I have noticed recently to be a subproblem in many string dp problems, especially one where you want to either "include" or "exclude" a certain substring when considering your answers.

This problem is "maximum prefix of S that matches given i characters already match and we add the character c". Basically it is useful because at each point in our dp we want to know how many characters we are matching (how much we progress to a good/invalid state).

For example:

S = "lololol"

i = 3, c = 'z' would represent "lolz", and the match would be 0

i = 3, c = 'o' would represent "lolo", and the match would be 4 because it matches with the prefix " lolo lol"

Slightly better example)

Naive O(alphabet * N^3) solution is to loop every size, (a-z), then try every prefix size, and compare string in O(N). This can become O(N^2) with hashing or some string algorithm (what I had to resort to, but it is a pain).

However, there seems to be an easy to write DP solution.

The DP is briefly mentioned in this div3 tutorial (but with only 2 characters): http://codeforces.com/contest/1015/problem/F

However, solution code does not contain an implementation of it.

After some digging, I found tutorial to this problem used exactly same dp.

DP[i][char] represents value as defined above.

Implementation of tutorial looks something like this (notice pattern is zero indexed, so i-1 is the i'th character):

Code

So maybe I am just slow, but it really does seem like magic right now!

Now I want to ask, what is the idea behind this O(N) dp. For example, why is it always optimal to build off prev, and what exactly does prev represent (I'm assuming it is the biggest match beforehand excluding a full match).

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

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by brdy (previous revision, new revision, compare).

»
15 months ago, # |
  Vote: I like it -47 Vote: I do not like it

You don't need to be a LGM to solve this problem

You are just a newbie!

  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    String problem are really one of my weaknesses, so maybe that is why I cannot understand such a "simple" dp. I get the general idea, I just don't fully understand it.

»
15 months ago, # |
  Vote: I like it +14 Vote: I do not like it

I think what you are missing is the KMP Algorithm. This Dp is quite straight forward after that

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I studied KMP, now I will share my updated (and hopefully correct understanding) here.

Prev represents the longest proper suffix that is a prefix (lps), otherwise known as the "fail function" of a normal KMP prefix function.

In normal kmp, we need a loop to go down every partial lps, but since we are doing a dp the recurrence handles it. Basically (like normal KMP) we try to expand the lps by the new character.