Câu 10. SOẠN VĂN BẢN vanban.cpp Đúng lúc An hào hứng làm bài tập tin học nhất thì bàn phím lại bị hỏng: chỉ gõ được các ký tự chữ cái. Nhiệm vụ của An là soạn thảo một văn bản chỉ sử dụng từ trong một danh sách cho trước. An quyết định vẫn làm bài tập trên máy của mình, sau đó copy sang máy của một bạn khác trong lớp và chèn thêm dấu cách vào giữa các từ, giữa hai từ sẽ chèn đúng một dấu cách. Như vậy ít ảnh hưởng đến thời gian sử dụng máy của bạn nhất. Ví dụ: với n = 5 và danh sách các từ cho trước là an, anh, han, tin, hoc; An soạn sẵn dòng anhanhoctin, sau đó mang sang máy của bạn và chèn thêm dấu cách thành anh an hoc tin. Tuy nhiên khi bắt tay vào chèn dấu cách, An mới nhận thấy rằng vấn đề cũng không đơn giản vì có thể có nhiều cách, thậm chí có thể không có cách chèn nếu gõ văn bản sai.Ví dụ: với dòng anhanhoctin ta có một cách đặt dấu cách khác thỏa mãn là: an han hoc tin. Yêu cầu: Cho từ và một xâu S không có dấu cách. Hãy xác định số cách chèn kí tự trắng (dấu cách) vào xâu S để được một văn bản chỉ gồm các từ có trong từ đã cho. Dữ liệu: - Dòng đầu tiên chứa số nguyên n (1 < n 100). - dòng sau: mỗi dòng chứa một từ được sử dụng (mỗi từ không quá 20 ký tự, các từ khác nhau từng đôi một). - Dòng cuối cùng là xâu S chứa không quá 100 kí tự. Kết quả: một số nguyên xác định số cách chèn dấu cách, nếu không có cách chèn theo yêu cầu thì ghi ra số 0. Ví dụ: INPUT OUTPUT 5 anh an han hoc tin anhanhoctin 2 (Giải thích: Hai cách đặt dấu cách là: anh an hoc tin; an han hoc tin)