Longest Common Prefix (LCP)

Problem definition

The length of the longest common prefix of two strings A[0..m) and B[0..n), denoted by lcp(A,B), is the largest integer $k \leq min\{m,n\}$ such that A[0..k)=B[0..k). In this homework, we need to build a data structure that can compute LCP efficiently.

First of all, we need to construct a large set of strings, as follows.

• We define that the 0'th string is a empty string.
• For the i'th string, it is one of previous strings (The p'th string where $0 \leq p < i$) with a lower case English letter appended to it.

• The first string is “a”, which is the 0'th string with ‘a’ appended to it.
• The second string is “ab” , which is the first string with ‘b’ appended to it.
• The third string is “abc”, which is the second string with ‘c’ appended to it.
• The forth string is “abd”, which is the second string with ‘d’ appended to it.

I/O formats

• Input format
  • The first line contain a single integer n , which denotes the number of strings.
  • For the next n line, the i'th line decribes the i'th string. In i'th line , there’re a integer l and a character c, which means that the i'th string is the l'th string with c appended to it.
  • The next line contain a single integer q, which denotes the number of questions.
  • In each of next q line, there’re two integer i, j , which means that you are asked to output the lcp( i'th string, j'th string ).
• Output format

  For each question, output the anser of it in a line.

• Limits
  • $n \leq 2 \times 10^5$
  • $q \leq 5 \times 10^6$

I/O Examples

• Sample input file 10 0 e 0 f 2 f 2 f 2 e 0 e 3 e 2 f 1 f 6 f 10 1 1 8 10 10 9 1 3 10 2 7 2 7 4 1 6 1 5 6 3
• Sample Output file 1 0 2 0 0 1 2 1 0 0

Open Test Sets

• sample_input.txt
• sample_output.txt

Hints and Suggestions

• If you use cin/cout, please add “ios_base::sync_with_stdio(0); cin.tie(0);” in the beginning of main function, and don’t use any scanf/printf.
• LCA的倍增算法
  • 簡略版，首推建中講義 4.3節 (陳冠宇高三的時候寫的)
  • 詳細版