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 integers a and b. You must answer the length of the ELCS of the a-th string and b-th string.

Input

First line consists one integer N.

Next N lines consist N strings.

Next line consists one integer Q.

Next Q lines consist two integers a and b. (0 <= a, b < N)

30% of the test data: N <= 100 Q <= 10000, length(string[i]) <= 100

100% of the test data: 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

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

hide comments
2016-10-18 23:12:49 Jaber Ahmed
i m using longest common substring approach. Bt got WA.complexity 0(m*n).any other algorithm to solve this problem.please suggest me.
2015-09-05 23:52:16 Grzegorz Graczyk
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
2010-11-26 01:19:19 Alca
Robbin_Karp is really easy to get an AC.

Last edit: 2010-11-27 00:30:34
2010-08-16 07:51:28 ymGXX
Hash algorithm is very simple.

Last edit: 2010-09-17 01:57:08
2010-07-08 09:11:05 [Rampage] Blue.Mary
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
2010-06-14 01:09:04 anon
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
2010-05-18 23:42:38 Anshu Saurabh
N is always less than 100??
Reply: N <= 100000

Last edit: 2010-05-18 23:44:10
2010-05-18 23:42:38 Damir Ferizovic
It would be better without those percentages. Just make bounds for N , Q , and len.
Reply: :)

Last edit: 2010-05-19 20:21:48
2010-05-18 23:42:38 Kinan Sarmini
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
2010-05-18 23:42:38 hosam samy
does the first line contain one or two integers ?
Reply : One. See the input format. :)

Last edit: 2010-05-18 12:23:56
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.