ankdroid's blog

By ankdroid, history, 5 years ago, In English

Obsessive String The first part of substring search(using KMP ) is clear. I was going through the editorial but the DP state is unclear to me. Is it some standard counting technique. If yes could anyone provide similar problem links ?

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

»
5 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

I just did this problem, and I agree that the editorial is a but unclear.

Let's just have one dp array. dp[i] counts the number of ways to be at the following position: "we haven't decided what to do with character i yet, but we have decided for stuff before i."

At character i, we can ignore it and move to i+1. This is easy: dp[i+1] += dp[i].

At character i, we can also choose to take it. Let f denote the first index (f>=i) such that the substring from f to f+T-1 is equivalent to T. Notice that if we take i, we always have to take up to f+T-1 as well. This means that we can only choose a substring which ends at f+T-1 to S. Therefore, we do a range update (suppose with a segment tree) from f+T to S+1 inclusive (add dp[i] to this range).

If this isn't clear yet maybe go back and convince yourself why this works.

Now we want to make this O(N) because segment tree solution is O(N log N). Notice that you are going through the array one index by one index and you always add to values after yourself. This means we can use a prefix sum which we maintain as we go.

Specifically, we keep delta[] array, and if we want to update from f+T to the end, we simply do delta[f+T] += dp[i]. Then, at each index, we keep a prefix sum (call it cur), and do cur += delta[i]. Notice that after this, cur is actually the value which you would normally query from the range tree. Try convince yourself of this.

Then, obviously we have a dp array, and we simply read the value from dp[S+1] (because that means we are about to do character S+1 which doesn't exist, so we are finished).

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

    Thanks for answering. "At character i, we can ignore it and move to i+1."

    Instead of dp[i+1] += dp[i] Shouldn't it be dp[i] += dp[i-1]

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      No, dp[i] is the value if we haven't considered i yet. Because we just considered i, we need to update dp[i+1].

      In other words dp[x] means ignore everything strictly before x.