Tất cả thử thách
Khó 1 đã giải Tỷ lệ chấp nhận 100.0%

Tìm Nhiều Mẫu Trong Văn Bản

Với mỗi mẫu được yêu cầu, xác định xem nó có xuất hiện dưới dạng một chuỗi con liên tiếp ở bất kỳ đâu trong văn bản chung hay không.

Bạn sẽ học được gì

  • Kiểm tra nhiều mẫu trên một văn bản thật nhanh
  • Tiền xử lý văn bản hoặc mẫu để tra cứu nhanh
  • So sánh tìm kiếm ngây thơ với tìm kiếm có chỉ mục

Đề bài

Xem bản gốc (English)

Với mỗi mẫu được yêu cầu, xác định xem nó có xuất hiện dưới dạng một chuỗi con liên tiếp ở bất kỳ đâu trong văn bản chung hay không. Các mẫu có thể chồng lặp và có thể lặp lại. Trả về kết quả theo đúng thứ tự truy vấn ban đầu. Giới hạn yêu cầu một phương pháp có thể xử lý hiệu quả nhiều mẫu.

Cài đặt find_many_patterns(text, patterns).

Đầu vào

text: Văn bản được tìm kiếm bởi mọi truy vấn.

patterns: Các mẫu, theo thứ tự truy vấn.

Đầu ra

Trả về YES cho mỗi mẫu xuất hiện và NO cho mỗi mẫu không xuất hiện.

Ràng buộc

1…100.000 ký tự văn bản. 1…100.000 mẫu không rỗng, với tổng độ dài tối đa 500.000. Tất cả ký tự đều là chữ thường a–z.

Ví dụ

Ví dụ 1
Đầu vào:
text = "bananas"
patterns = ["ana", "apple", "nas"]

Kết quả mong đợi:
expected = ["YES", "NO", "YES"]
Đầu vào:
std::string text = "bananas";
std::vector<std::string> patterns = {"ana", "apple", "nas"};

Kết quả mong đợi:
std::vector<std::string> expected = {"YES", "NO", "YES"};
Đầu vào:
string text = "bananas";
string[] patterns = new string[] {"ana", "apple", "nas"};

Kết quả mong đợi:
string[] expected = new string[] {"YES", "NO", "YES"};

Giải thích

Ana xuất hiện bắt đầu tại vị trí 2 và nas tại vị trí 5 (vị trí bắt đầu từ 1 ở đây). Apple không bao giờ xuất hiện.

Ví dụ 2
Đầu vào:
text = "aaaa"
patterns = ["aa", "aaaaa", "aa"]

Kết quả mong đợi:
expected = ["YES", "NO", "YES"]
Đầu vào:
std::string text = "aaaa";
std::vector<std::string> patterns = {"aa", "aaaaa", "aa"};

Kết quả mong đợi:
std::vector<std::string> expected = {"YES", "NO", "YES"};
Đầu vào:
string text = "aaaa";
string[] patterns = new string[] {"aa", "aaaaa", "aa"};

Kết quả mong đợi:
string[] expected = new string[] {"YES", "NO", "YES"};

Giải thích

Aa xuất hiện mặc dù có các lần khớp chồng lặp. Năm ký tự a không thể nằm trong một văn bản bốn ký tự. Truy vấn aa lặp lại nhận cùng một câu trả lời.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Nhiều pattern có thể dùng chung phần xử lý, nên đừng tìm từng query riêng trên text.

Gợi ý 2

Hãy xây một cấu trúc chứa tất cả pattern rồi quét text một lần, cập nhật các match khi ký tự đi qua.

Gợi ý 3

Chú ý báo các pattern lặp theo đúng thứ tự query, và cho phép các match chồng lấp được tính riêng.

Độ phức tạp mong đợi

thời gian O(text length + total pattern length), bộ nhớ phụ O(total pattern length)

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 848 ms - 4/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 1 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.