dcordb's blog

Could you help me with this strings problem?
By dcordb, 10 years ago, In English

This is a problem from COCI 2003, here I left you the link. The problem name is VOKI (it is the third in the pdf).

http://hsin.hr/2003/national/second_day/juniors/problems.pdf

So far I have a DP approach that works in O(n * m * max(n, m)) which is too slow, could you help me to improve this?

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

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What I understood from the problem is find the shortest sequence that exists in VOKI and dose not exist in TOKI.

It can be done in O(n * m * logm ) whenever you decide to include the ith letter of VOKI , do binary search to find the same letter in TOKI after or equal the jth letter . here is my solution http://ideone.com/bMBs68

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

    Can be done in O(n * m) also now nxt[i][j] denotes the next appearance of the ith letter after or equal to the jth index

    http://ideone.com/chXExW

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

    Could you explain it a little more? What I don't get is how do you guarantee that the subsequence isn't in TOKI. Also from your solution i and j are prefixes of VOKI and TOKI, right?

    → Reply