VWORDPOW - Sức mạnh của ngôn từ
Giới hạn- Thời gian: 0.159s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Nông dân John muốn đánh giá chất lượng các cái tên mà ông đã đặt cho N (1 <= N <= 1000) con bò của mình. Mỗi cái tên là một xâu ký tự có độ dài không quá 1000 ký tự và không có ký tự nào là ký tự trắng ( dấu cách ).
John đã lập nên 1 tập M xâu ‘tốt’ ( độ dài không quá 30 ký tự và hoàn toàn không có dấu cách ). Nếu một xâu ‘tốt’ là xâu con của tên 1 con bò ( các ký tự không nhất thiết phải liền kề nhau ) thì tên con bò đó được cộng 1 điểm chất lượng.
Tất cả các xâu là case-insensitive, tức là chữ hoa và chữ thường coi như giống nhau. Ví dụ tên “Bessie” chứa các xâu “Be”, “sI”, “EE”, và “Es” ,... là xâu con nhưng không chứa “is” hay “eB” là xâu con. Hãy giúp nông dân John xác định số lượng điểm chất lượng mà tên của mỗi con bò có được.
Dữ liệu
- Dòng 1: 2 số nguyên cách nhau bởi dấu cách: N và M
- Dòng 2..N+1: Dòng i+1 chứa 1 xâu ký tự là tên của con bò thứ i.
- Dòng N+2..N+M+1: Dòng N+i+1 chứa xâu ‘tốt’ thứ i.
Kết quả
- Dòng 1..N+1: Dòng i+1 chứa 1 số nguyên là điểm chất lượng của tên bò thứ i.
Ví dụ
Dữ liệu 5 3 Bessie Jonathan Montgomery Alicia Angola se nGo Ont Giải thích: Có 5 con bò, tên chúng là “Bessie”, “Jonathan”, “Montgomery”, “Alicia” và “Angola”. Có 3 xâu ‘tốt’ là “se”, “nGo” và “Ont”. Kết quả 1 1 2 0 1 Giải thích: "Bessie" có chứa "se", "Jonathan" chứa "Ont", "Montgomery" chứa cả "nGo" và "Ont", Alicia không chứa xâu tốt nào và "Angola" chứa "nGo".
- Người up: paulmcvn
- Nguồn bài: USACO US-Open 2008 - Bảng Bạc