Crazy LCP
시간 제한2초메모리 제한512 MB
N개의 문자열과 Q개의 구간 질의가 주어질 때, 각 구간 [L, R]에서 서로 다른 두 문자열이 가질 수 있는 최장 공통 접두사의 최댓값을 구한다.
문제
이 문제에서는 문자열 배열이 주어진다. 각 문자열에는 입력 순서대로 1부터 N까지의 고유한 번호가 붙는다. 이어서 Q개의 질의가 주어지며, 각 질의는 두 정수 L과 R로 이루어진다. 질의에 답하려면 L부터 R까지(양 끝 포함) 범위에서 서로 다른 번호를 가진 두 문자열을 골라, 그 두 문자열의 최장 공통 접두사의 길이가 가능한 모든 쌍 가운데 최대가 되도록 해야 한다.
입력
프로그램은 하나 이상의 테스트 케이스에 대해 실행된다. 입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 T (1 ≤ T ≤ 100)가 주어진다. 이어서 T개의 테스트 케이스가 따른다.
각 테스트 케이스는 정수 N (2 ≤ N ≤ 105)이 있는 줄로 시작하며, 그다음 줄에는 영문 소문자로만 이루어진 길이가 0이 아닌 문자열 N개가 공백 하나로 구분되어 주어진다. 각 테스트 케이스에서 문자열 길이의 합은 200,000을 넘지 않는다.
이어서 정수 Q (1 ≤ Q ≤ 105)가 있는 줄이 주어지며, 그다음 Q개의 줄 각각에는 위에서 설명한 질의를 나타내는 두 정수 L과 R이 공백 하나로 구분되어 주어진다 (1 ≤ L < R ≤ N).
출력
각 질의마다 위에서 설명한 최장 공통 접두사 길이의 최댓값을 한 줄에 하나씩 출력한다.
힌트
문자열 S의 접두사는 S의 왼쪽에서부터 0개 이상의 문자를 취한 문자열이다. 두 문자열의 공통 접두사는 두 문자열 모두의 접두사인 문자열이다.