| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT137C - BÀI C - ĐẾM XÂU CON THEO TỪ ĐIỂN |
Cho một xâu ký tự và một danh sách các từ, được gọi là từ điển. Bài toán đặt ra là hãy đếm xem từ xâu ban đầu có thể tổ hợp ra bao nhiêu xâu con trùng với các từ trong từ điển. Chú ý: một từ trong từ điển có thể có nhiều cách tạo xâu con từ xâu ban đầu, và nhiệm vụ của ta là phải đếm hết tất cả các cách đó.
Ví dụ với xâu là CHEVROLET, các từ trong từ điển là “he” và “vet” thì ta sẽ có 4 cách tạo xâu con tương ứng là:
.HE......
.H.....E.
...V...ET
.HEV...ET
Trong ví dụ trên, trường hợp cuối cùng là một từ ghép từ 2 từ trong từ điển. Tuy nhiên, chú ý trong trường hợp ghép từ thì phải đảm bảo từ ghép đó thực sự xuất hiện đúng thứ tự trong xâu ban đầu. Ví dụ với xâu CHEVROLET và hai từ là “hoe” và “vet” thì các từ này có thể tìm thấy riêng lẻ chứ không thể là từ ghép.
Input
• Dòng đầu tiên chứa số n là số bộ test (không quá 100). Mỗi bộ test gồm một số nguyên X, một khoảng trống, sau đó là một xâu ký tự S. Trong đó X là số từ trong từ điển (không quá 200000), S là xâu đầu vào (không quá 30 ký tự).
• X dòng tiếp theo, mỗi dòng ghi ra một từ trong từ điển (độ dài không quá 30).
Output
- Với mỗi bộ test, in ra màn hình, trên một dòng, duy nhất một số nguyên là số cách tạo ra các từ trong từ điển từ xâu ban đầu. Số này được đảm bảo không quá 300000.
Example
Input:
2
2 TOYOTA
toy
yo
5 CHEVROLET
does
he
like
her
program
Output:
2
3
| Được gửi lên bởi: | adm |
| Ngày: | 2013-03-24 |
| Thời gian chạy: | 5s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
