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
↵
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
