ELCS - Easy Longest Common Substring

no tags 

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.

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 a-th string and b-th string

Example

Input:

5

dy

ljq

lqp

ws

jzt

3

0 1

1 2

0 2

Output:

0

1

0


hide comments
Jaber Ahmed: 2016-10-18 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: 2015-09-05 23:52:16

Very important hint for this task:

Cin causes cout to flush by default. And time limit in this task is not enough for 100000 flushes.

Last edit: 2015-09-06 00:21:16
Alca: 2010-11-26 01:19:19

Robbin_Karp is really easy to get an AC.

Last edit: 2010-11-27 00:30:34
ymGXX: 2010-08-16 07:51:28

Hash algorithm is very simple.

Last edit: 2010-09-17 01:57:08
[Rampage] Blue.Mary: 2010-07-08 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?)

Edit: (by [Trichromatic]XilinX) Yes, it's very silly :)

RE: hashing is NOT the only way to pass :)

Re: (by [Trichromatic]XilinX) Yes, thinking about the essence of suffix tree lead you to the easier algorithm...

Last edit: 2010-07-09 14:30:17
anon: 2010-06-14 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

Reply:max{length(string[i])}<=5*10^5

Last edit: 2010-06-14 04:44:27
Anshu Saurabh: 2010-05-18 23:42:38

N is always less than 100??
Reply: N <= 100000

Last edit: 2010-05-18 23:44:10
Damir Ferizovic: 2010-05-18 23:42:38

It would be better without those percentages. Just make bounds for N , Q , and len.
Reply: :)

Last edit: 2010-05-19 20:21:48
Kinan Sarmini: 2010-05-18 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...
Reply: 30% of the testdata : N<=100
It doesn't mean that 100% of the testdata N<=100

Last edit: 2010-05-18 12:50:20
hosam samy: 2010-05-18 23:42:38

does the first line contain one or two integers ?
Reply : One. See the input format. :)

Last edit: 2010-05-18 12:23:56

Added by:刘启鹏
Date:2010-05-18
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