Hello everyone! I need help in this problem!
LINK to the problem.
There are two strings s and t. Find the longest string which is a substring of s and t. If there are many solutions print the first one appear in the string t.
I am one of the coders who use suffix array to solve this problem but got WAs. And the editorial to this question mentioned two ways to solve the problem without suffix array. And it's really annoying that I still don't get why my code was wrong after read the DISCUSS about this.
Please help me! Can you challenge my code?
I'd like to explain my solution first so that you can come up with some test cases that my code will fail.First as the typical suffix array's solution will do, I calculate the suffix array and lcp array of the connected string which is sa and hg in my code. Then I use binary search to get the length of the answer and get the position in the mean time. And each time check if there's a substring whose length is bigger or equal to the number we check right now. During this I separate the array of lcp into many groups each is a group consists of continued hg[i] which is bigger or equal to the number wo check right now. And if there is a group in which there is a sa[i] < ls and another sa[j] > ls, then the number we check right now is OK. (Ps, ls is the length of the first string.)This solution work in O(nlogn) I think.
Here is my code.
Is there any mistake? Please enlighten me. Thanks a lot.