I was trying this question and i got WA at case 3. Problem Link:- http://acm.timus.ru/problem.aspx?space=1&num=1713
My approach includes constructing a suffix array on string formed by concatenating all the strings(commands) given in the input.
Then for each index belonging to the command i am calculating the max value of LCP that can be formed using other indexes belonging to other commands. For doing that i am calculating the closest indexes to that index not belonging to the same command using the Array sorted in order of suffixes.
For any command the answer of that command will be the smallest value of LCP of indexes belonging to that command described as above .
I am unable to find any bug . So please Help ......
This is my code :- http://ideone.com/8veKxE
This is my first post , so kindly ignore any mistakes .
You can write any easy-to-code solution, generate some small random test cases and compare the answers. This should help you to find your bug.
Do you know any solution better than for O(107)?
O(10^7)isO(1)!You're very clever, yes?
yes!!!!
Thanks a lot for the suggestion. I was able to figure out my mistake by generating random cases . :)