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…n1] and s2[0…m1], the ELCS of them is a string p[0…k1] 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 ath string and bth string.
Input
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
Output
Q lines. Each line consists the length of the ELCS of the ath string and bth string
Example
Input:5
dy
ljq
lqp
ws
jzt
3
0 1
1 2
0 2
Output:0
1
0
hide comments
Jaber Ahmed:
20161018 23:12:49
i m using longest common substring approach. Bt got WA.complexity 0(m*n).any other algorithm to solve this problem.please suggest me. 

Grzegorz Graczyk:
20150905 23:52:16
Very important hint for this task:


Alca:
20101126 01:19:19
Robbin_Karp is really easy to get an AC. Last edit: 20101127 00:30:34 

ymGXX:
20100816 07:51:28
Hash algorithm is very simple. Last edit: 20100917 01:57:08 

[Rampage] Blue.Mary:
20100708 09:11:05
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?)


anon:
20100614 01:09:04
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


Anshu Saurabh:
20100518 23:42:38
N is always less than 100??


Damir Ferizovic:
20100518 23:42:38
It would be better without those percentages. Just make bounds for N , Q , and len.


Kinan Sarmini:
20100518 23:42:38
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...


hosam samy:
20100518 23:42:38
does the first line contain one or two integers ?

Added by:  刘启鹏 
Date:  20100518 
Time limit:  0.136s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  my own problem 