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

Auto comment: topic has been updated by Zeus726 (previous revision, new revision, compare).Here's a hint:

Build the trie for all

s_{i}. It will haveO(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.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.