시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 93 | 16 | 9 | 15.789% |
알파벳 소문자로만 이루어진 $N$개의 문자열 $S_1, \dots, S_N$이 주어진다. 아래의 쿼리를 처리하는 프로그램을 작성하시오.
어떤 문자열의 부분 문자열은 그 문자열의 비어있지 않은 연속한 부분으로 정의한다.
두 문자열 $A$와 $B$의 공통 부분 문자열은 $A$의 부분 문자열이면서 $B$의 부분 문자열인 문자열이다.
첫째 줄에 문자열의 개수 $N$이 주어진다. ($1 \leq N \leq 200\,000$)
이어지는 $N$개의 줄에, 알파벳 소문자로 이루어진 문자열 $S_1, \dots, S_N$이 한 줄에 하나씩 주어진다. $S_1, \dots, S_N$의 길이의 합은 $200\,000$을 넘지 않음이 보장된다.
이어지는 줄에 쿼리의 개수 $Q$가 주어진다. ($1 \leq Q \leq 200\,000$)
이어지는 $Q$개의 줄에 쿼리를 나타내는 두 정수 $i$와 $j$가 주어진다. ($1 \leq i, j \leq N$)
각 $Q$개의 쿼리에 대한 정답을 한 줄에 하나씩 순서대로 출력한다.
5 melon lemon apple grape peach 5 1 2 4 5 2 4 3 4 3 3
6 4 1 4 14
1번째 쿼리에서, $\textrm{"melon"}$과 $\textrm{"lemon"}$의 서로 다른 공통 부분 문자열은 $\textrm{"e", "l", "m", "n", "o", "on"}$ 이 있다. 따라서 6을 출력해야 한다.
4번째 쿼리에서, $\textrm{"apple"}$과 $\textrm{"grape"}$의 서로 다른 공통 부분 문자열은 $\textrm{"a", "e", "p", "ap"}$가 있다. 따라서 4를 출력해야 한다.
5번째 쿼리에서, $\textrm{"apple"}$와 $\textrm{"apple"}$의 서로 다른 공통 부분 문자열은 $\textrm{"a", "e", "l", "p", "ap", "le", "pl", "pp", "app", "ple", "ppl", "appl", "pple", "apple"}$가 있다. 따라서 14를 출력해야 한다. 두 번 등장하는 $\textrm{"p"}$를 한 번만 세었음에 유의하라.
4 sunrin high school olympiad 5 1 3 2 2 2 4 3 2 4 1
1 9 1 1 1