Zeus726's blog

a problem with strings
By Zeus726, history, 6 years ago, In English

Hello every one ...

I have a simple problem from inoi(Iran national Olympiad in Informatics)

I've a solution for it but i'm looking for a better solution.

you have m bad strings(sum of lengths <= 200) and integers n <= 1e5, q <= 1e5 and a char k <= 'z'

we build n strings like this with lower bound English letters :

for i from 1 to n :

s[i] is that string that the size of it is minimum possible and all of its characters are smaller than or equal to k and it doesn't contain any bad string as a sub string and after all, all the n strings should be unique!

among those suitable strings for s[i] we choose that who's lexicographically minimum.

after that you should answer q queries :

1 x y : what is the length of the longest common prefix of the s[x] and s[y]

2 x y : print the longest common prefix of s[x] and s[y]

it's guaranteed that there's at most 40 queries of type 2.

thanks in advance

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

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Here's a hint:

Build the trie for all si. It will have O(n) vertices. And you can keep an array of size 200 for every vertex in this trie to keep the hashes of each suffix from 1 to 200.

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

    hmmm...

    thanks for your respond!

    my solution is like what you've said i think!

    but :

    the solution that I've found was with aho-corasick

    we use aho for bad strings.

    we can build a bfs tree with root: empty string (for the s[i])

    for every node we can check to add a char at the end of it and move with o(1) in another tree that were built for aho and check if its valid or not.

    → Reply