Chọn Đội tuyển HSGQG Huế 2024 - RNA
Xem dạng PDF
Ribonucleic acid (RNA) là một phân tử polymer cơ bản có nhiều vai trò sinh học trong mã hóa, dịch mã, điều hòa, và biểu hiện của gene. RNA là một loại nucleic acid, và, cùng với lipid, protein và carbohydrate, tạo thành bốn loại đại phân tử cơ sở cho mọi dạng sự sống trên Trái Đất.
Giống như DNA, RNA tạo thành từ một chuỗi nucleotide, nhưng không giống DNA là thường tìm thấy nó ở dạng tự nhiên là một sợi đơn gập lại vào chính nó, hơn là sợi xoắn kép. Các sinh vật tế bào sử dụng RNA thông tin (mRNA) đề truyền đạt các thông tin di truyền (sử dụng các base nitric guanine, uracil, adenine, và cytosine, ký hiệu tương ứng bằng các chữ cái G, U, A và C) cho phép tổng hợp trực tiếp lên các protein chuyên biệt. Nhiều virus mã hóa thông tin di truyền của chúng trong bộ gene RNA.
Một nhà khoa học ~K~ muốn nghiên cứu các đặc tính của ~n~ chuỗi RNA khác nhau mà phòng thí nghiệm hiện có. Biết rằng các RNA có chung các nucleotide ở đầu hoặc ở cuối chuỗi thường sẽ có các tính chất tương tự nhau, ~K~ thực hiện ~m~ thao tác trích xuất RNA với các yêu cầu: ứng với một thao tác trích xuất, ~K~ cần thu thập tất cả các chuỗi RNA:
Nhận xâu ~P~ làm một tiền tố, và
Nhận xâu ~Q~ làm một hậu tố.
Trong đó, ~P~, ~Q~ là đặc trưng của thao tác trích xuất được cho trước.
Với mỗi một thao tác trích xuất, bạn hãy xác định giúp ~K~ rằng có bao nhiêu chuỗi RNA thoả mãn các yêu cầu trên.
Input
Dòng đầu tiên chứa hai số nguyên dương ~n, m~, cách nhau bởi một dấu cách (~1 \leq n, m \leq 10^5~).
~n~ dòng tiếp theo, dòng thứ ~i~ chứa xâu ~S_i~ (~1 \leq i \leq n~, ~1 \leq |S_i| \leq 10^5~).
~m~ dòng tiếp theo, dòng thứ ~j~ chứa hai xâu đặc trưng của thao tác trích xuất ~P_j, Q_j~, cách nhau bởi một dấu cách (~1 \leq j \leq m~, ~1 \leq |P_j|, |Q_j| \leq m~).
~\sum |S_i|, \sum |P_j|, \sum |Q_j| \leq 2 \cdot 10^6~.
Output
Xuất ra file ~m~ dòng, dòng thứ ~j~ chứa một số nguyên là kết quả của thao tác trích xuất thứ ~j~.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| ~1~ | ~36 \%~ | ~n, m, \lvert S_i \rvert, \lvert P_j \rvert, \lvert Q_j \rvert \le 100~ |
| ~2~ | ~28 \%~ | ~n, m \le 5 \times 10^3~ |
| ~3~ | ~12 \%~ | ~\sum \lvert S_i \rvert, \sum \lvert P_j \rvert, \sum \lvert Q_j \rvert \le 10^5~ |
| ~4~ | ~24 \%~ | Không có giới hạn gì thêm |
Sample Input 1
2 3
AUGC
AGC
G C
AU C
A C
Sample Output 1
0
1
2
Sample Input 2
3 3
AA
AA
AGA
AA AA
AG GA
AG GA
Sample Output 2
2
1
1
Notes
Sample 1:
Thao tác 1: Không có RNA nào bắt đầu bằng G.
Thao tác 2: AU|G|C thỏa mãn
Thao tác 3: Cả hai xâu đều thỏa mãn
Sample 2:
- Thao tác 2: Xâu AGA vẫn thỏa mãn, mặc dù hai xâu P = AG và Q = GA bị chồng lên nhau khi xếp trên xâu ban đầu.
Bình luận