selling_rna

Selling RNA Strands

Selling RNA Strands

Just Odd Inventions Co., Ltd를 알고 있는가? 이 회사의 사업은 “그저 기묘한 발명”을 하는 것이다. 여기서는 회사 이름을 줄여서 JOI Company라고 부르겠다. 최근 JOI Company은 그저 기묘한 발명만 하면서 수익성이 심각하게 악화되었다. 이 회사는 새로운 사업을 시작할 계획이다. 그 계획은 RNA 사슬이 들어 있는 액체를 판매하는 것이다. RNA 사슬은 4개의 문자 ‘A’, ‘G’, ‘C’, ‘U’로 이루어진 문자열로 간주한다. 이 사업을 위해 JOI Company은 N개의 RNA 사슬을 준비한다. JOI 회사는 고객으로부터 다음 형식으로 RNA 사슬 주문을 받는다.

• 고객은 두 문자열 P, Q를 선택한다. 그러면 JOI Company이 준비한 RNA 사슬 중에서 처음 |P|개의 문자가 P이고 마지막 |Q|개의 문자가 Q인 문자열을 판매한다. 여기서 |P|, |Q|는 각각 P, Q의 길이이다.

JOI Company이 준비한 RNA 사슬 중 고객의 주문 조건과 일치하는 것은 몇 개인가?

JOI Company이 준비한 RNA 사슬과 고객의 주문에 관한 정보가 주어질 때, JOI Company이 준비한 RNA 사슬 중 고객의 주문 조건과 일치하는 사슬의 개수를 계산하는 프로그램을 작성하라.

제약 조건

모든 입력 데이터는 다음 조건을 만족한다.

• 1 ≤ N ≤ 100 000.

• 1 ≤ M ≤ 100 000.

• 각 문자열은 4개의 문자 A, G, C, U로 이루어진다.

• 1 ≤ |S i | ≤ 100 000 (1 ≤ i ≤ N).

• 1 ≤ |P j | ≤ 100 000 (1 ≤ j ≤ M).

• 1 ≤ |Q j | ≤ 100 000 (1 ≤ j ≤ M).

• |S 1 | + |S 2 | + . . . + |S N | ≤ 2 000 000.

• |P1 | + |P2 | + . . . + |P M | ≤ 2 000 000.

• |Q1 | + |Q2 | + . . . + |Q M | ≤ 2 000 000.

서브태스크

서브태스크 1 [10점] 다음 조건을 만족한다.

• N ≤ 100.

• M ≤ 100.

• |S i | ≤ 100 (1 ≤ i ≤ N).

• |P j | ≤ 100 (1 ≤ j ≤ M).

• |Q j | ≤ 100 (1 ≤ j ≤ M).

서브태스크 2 [25점] 다음 조건을 만족한다.

• N ≤ 5 000.

• M ≤ 5 000.

Selling RNA Strands

서브태스크 3 [25점] 다음 조건을 만족한다.

• |S 1 | + |S 2 | + . . . + |S N | ≤ 100 000.

• |P1 | + |P2 | + . . . + |P M | ≤ 100 000.

• |Q1 | + |Q2 | + . . . + |Q M | ≤ 100 000.

서브태스크 4 [40점] 추가 제약 조건은 없다.

표준 입력에서 다음 데이터를 읽는다.

• 입력의 첫 번째 줄에는 공백으로 구분된 두 정수 N, M이 주어진다. 이는 JOI Company이 N개의 RNA 사슬을 준비하고, 고객의 주문이 M개 있음을 의미한다.

• 이어지는 N개 줄의 i번째 줄에는(1 ≤ i ≤ N) 문자열 S i 가 주어지며, 이는 JOI Company이 준비한 i번째 RNA 사슬이다.

• 이어지는 M개 줄의 j번째 줄에는(1 ≤ j ≤ M) 공백으로 구분된 두 문자열 P j , Q j 가 주어진다. 이는 j번째 주문에서 고객이 두 문자열 P j , Q j 를 선택함을 의미한다.

출력은 M개의 줄로 이루어진다. j번째 줄에는(1 ≤ j ≤ M) JOI Company이 준비한 RNA 사슬 중 j번째 주문의 조건과 일치하는 사슬의 개수를 나타내는 정수를 출력한다.

Selling RNA Strands