ELCS - Easy Longest Common Substring
In this problem, a string only consists of lowercase letters.
Substring, is a consecutive sequence of characters occurrences at least once in a string.
Common substring means a substring of two strings.
After getting TLE on LCS and LCS2, lqp18_31 felt really depressed. So he came up with an interesting idea. He want to modify the definition of LCS and call it ELCS.
ELCS: for two given strings s1[0…n-1] and s2[0…m-1], the ELCS of them is a string p[0…k-1] k<=min(n,m) so that s1[i]=s2[i]=p[i] ( for 0<=i<k ) and s1[k]!=s2[k] or k==n or k==m .
Now your task is easy.
You are given N strings and Q queries.
Each query consists two intergers a and b. You must answer the length of the ELCS of the a-th string and b-th string.
Firtst line consists one interger N.
Next N lines consist N strings.
Next one line consists one interger Q.
Next Q lines consist two intergers a and b. (0<=a,b<N)
30% of the testdata : N<=100 Q<=10000 length(string[i])<=100
100% of the testdata : the number of total characters<=500000 N<=100000 Q<=100000
Q lines. Each line consists the length of the ELCS of the a-th string and b-th string
i m using longest common substring approach. Bt got WA.complexity 0(m*n).any other algorithm to solve this problem.please suggest me.
Very important hint for this task:
Robbin_Karp is really easy to get an AC.Last edit: 2010-11-27 00:30:34
Hash algorithm is very simple.Last edit: 2010-09-17 01:57:08
Er, building suffix array (without RMQ ST)takes ~1 second. Maybe hashing is the only way to pass. (Isn't this kind of problem very silly?)
Is there an upper bound for length(string[i]) in 100% of cases? The only one I can infer from the problem statement is 500000
N is always less than 100??
It would be better without those percentages. Just make bounds for N , Q , and len.
Can you please check the tests? I asserted every single line of the code, nothing is out of bounds everything seems normal, but still SIGSEGV...
does the first line contain one or two integers ?