문제
A, G, C, U로만 이루어진 문자열 N개가 주어진다.
이제 Q개의 쿼리를 처리해야 하는데, 각 쿼리는 문자열 X, Y로 이루어져 있으며,
주어진 N개의 문자열 중 접두사(prefix)가 X이고 접미사(suffix)가 Y인 문자열의 개수를 구해야 한다.
입력
첫 줄에 N과 Q가 주어진다. (1<=N,Q<=100000)
그 다음 N개의 줄에 걸쳐 문자열이 한 줄에 하나씩 주어진다.
이때 주어진 N개의 문자열의 길이의 합은 2000000을 넘기지 않는다.
그 다음 Q개의 줄에 걸쳐 각 쿼리를 나타내는 문자열 X, Y가 한 줄에 주어진다.
이때 주어진 Q개의 X의 길이의 합과, Q개의 Y의 길이의 합은 각각 2000000을 넘기지 않는다.
주어진 모든 문자열의 길이는 각각 100000을 넘기지 않는다.
Subtask #1 (25점) : N,Q<=100, 주어진 모든 문자열의 길이는 각각 100을 넘기지 않는다.
Subtask #2 (25점) : N,Q<=5000
Subtask #3 (25점) : 주어진 N개의 문자열의 합과, 주어진 Q개의 X/Y의 길이의 합은 각각 100000 이하이다.
Subtask #4 (25점) : 제한 없음
출력
Q개의 쿼리에 대한 답을 한 줄에 하나씩 출력하여라.
예제 #1
2 3
AUGC
AGC
G C
AU C
A C
0
1
2
예제 #2
8 7
GCGCUACCCCAACACAAGGCAAGAUAUA
G
GGAC
GCGG
U
GCGCUACCCCAACACAAGGCAAGAUGGUC
GCCG
GCGCUGA
GCGCUACCC A
GCGCUACCCC AC
GCG C
GCGC A
G G
G C
G GGA
1
0
1
2
3
2
0
출처
JOI Open Contest 2016
로그인해야 코드를 작성할 수 있어요.