a problem with strings
Difference between en3 and en4, changed 0 character(s)
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 

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Zeus726 2018-07-11 15:41:17 0 Tiny change: 'n advance ' -> 'n advance \n\nupd:'
en3 English Zeus726 2018-07-11 07:57:01 18
en2 English Zeus726 2018-07-10 20:38:38 0 (published)
en1 English Zeus726 2018-07-10 20:38:14 949 Initial revision (saved to drafts)