Big-O Coding LogoBig-O Coding
Khóa họcLộ trìnhLuyện phỏng vấnThi đấuBài tậpBảng xếp hạngAI Coding LabSắp ra mắtPremium
Quay lại
Đề bài
|
Lời giải
|
Bài nộp
|
Thảo luận (0)

Kiểm tra từ bắt đầu bằng tiền tố bằng cây Trie

Easy 256MB

Cho một danh sách gồm NNN từ W1,W2,…,WNW_1, W_2, \dots, W_NW1​,W2​,…,WN​, mỗi từ là một chuỗi ký tự không rỗng chỉ gồm các chữ cái tiếng Anh viết thường ('a' đến 'z').

Sau đó, bạn cần xử lý QQQ truy vấn. Ở mỗi truy vấn, bạn được cung cấp một chuỗi tiền tố không rỗng PPP.

Nhiệm vụ của bạn là kiểm tra xem trong danh sách NNN từ ban đầu có tồn tại ít nhất một từ bắt đầu bằng tiền tố PPP hay không.

Một từ WWW được gọi là bắt đầu bằng tiền tố PPP nếu chuỗi PPP trùng với ∣P∣|P|∣P∣ ký tự đầu tiên của chuỗi WWW (nghĩa là ∣P∣≤∣W∣|P| \le |W|∣P∣≤∣W∣ và W[1..∣P∣]=PW[1..|P|] = PW[1..∣P∣]=P, trong đó các ký tự trong chuỗi được đánh số từ 111).

Đầu vào

Dòng đầu tiên chứa hai số nguyên NNN và QQQ (1≤N,Q≤1051 \le N, Q \le 10^51≤N,Q≤105). NNN dòng tiếp theo, dòng thứ iii chứa chuỗi không rỗng WiW_iWi​ biểu diễn từ thứ iii trong danh sách. QQQ dòng tiếp theo, dòng thứ jjj chứa chuỗi không rỗng PjP_jPj​ biểu diễn tiền tố cần kiểm tra trong truy vấn thứ jjj.

Mỗi chuỗi WiW_iWi​ và PjP_jPj​ có độ dài ít nhất 111 (1≤∣Wi∣,∣Pj∣1 \le |W_i|, |P_j|1≤∣Wi​∣,∣Pj​∣). Tổng độ dài của NNN từ WiW_iWi​ thỏa mãn 1≤∑∣Wi∣≤2⋅1051 \le \sum |W_i| \le 2 \cdot 10^51≤∑∣Wi​∣≤2⋅105. Tổng độ dài của QQQ tiền tố PjP_jPj​ thỏa mãn 1≤∑∣Pj∣≤2⋅1051 \le \sum |P_j| \le 2 \cdot 10^51≤∑∣Pj​∣≤2⋅105. Các chuỗi chỉ chứa ký tự tiếng Anh viết thường từ 'a' đến `'z'.

Đầu ra

In ra QQQ dòng, dòng thứ jjj in ra YES nếu tồn tại ít nhất một từ trong danh sách bắt đầu bằng tiền tố PjP_jPj​, ngược lại in ra NO.

Ví dụ 1

Đầu vào

4 3
apple
app
apply
cat
app
ap
dog

Đầu ra

YES
YES
NO

Ví dụ 2

Đầu vào

3 2
banana
band
bandit
ba
banda

Đầu ra

YES
NO
Chỉ viết thân hàm, hệ thống tự lo Input/Output
Bài này không hỗ trợ chế độ Viết chương trình
Bật gợi ý code
|
Loading...
Test Case
|
Output
Ln 1, Col 1
Đang tải test ví dụ...