﻿ Fuzhou University OnlineJudge ﻿
Problem 1985 LCP Problem

## Problem Description

LCP (Longest Common Prefix), is defined as the longest common prefix of two strings. For example, LCP (“AC”, “ACOrz”) = “AC”, LCP (“WA”,”AC”) = “”.

Now you are given several DNA sequence. (Only contains ‘A’, ‘T’, ‘C’ and ‘G’).

You are expected to output the length of the LCP of two DNA sequence.

## Input

In the first line there is an integer T, indicates the number of test cases. (T <= 10)

In each case, the first line contains only one integer n, indicates the number of DNA sequence. (1 <= n <=100000, the number of letters in one test case is smaller than 100000)

Then one integer m, then m lines, each line contains two integers a,b ,indicates the index of the two DNA sequence. (0 <= m <= 100000, 0<= a,b <n)

## Output

For each case, output “Case idx: “first where idx is the case index start from 1 in a single line , then output m lines indicate the length of the LCP.

## Sample Input

2 2 ATCG AT 1 0 1 3 AT ATT ATTT 3 0 0 0 1 0 2

## Sample Output

Case 1: 2 Case 2: 2 2 2

## Source

FOJ有奖月赛-2010年11月

Submit  Back  Status  Discuss
﻿