Блог пользователя brdy

Автор brdy, история, 6 лет назад, По-английски

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).

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -47 Проголосовать: не нравится

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

You are just a newbie!

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.