MCONSTR - Search of Concatenated Strings
Giới hạn- Thời gian: 2.442s
- 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.
Có nhiều phiên bản về bài toán tìm kiếm từ khóa trong một chuỗi. Nếu chỉ tìm một xâu trong một đoạn văn bản thì đã có thuật toán chuẩn. Nếu mẫu tìm kiếm gồm nhiều xâu con hoặc được mô tả bằng các biểu thức chính quy thì cần các thuật toán phức tạp hơn.
Trong bài toán này, một số xâu cơ bản được cho trước, nhưng chúng ta không tìm kiếm trực tiếp trên chúng mà tìm kiếm các xâu thu được bằng việc ghép chúng theo thứ tự bất kỳ.
Ví dụ, cho ba xâu cơ bản là aa, b và ccc. Chúng ta phải tìm kiếm 6 xâu sau trong đoạn văn bản.
aabccc aacccb baaccc bcccaa cccaab cccbaa
Các xâu này có thể xuất hiện nhiều lần trong văn bản và bạn phải đếm số lần xuất hiện đó. Hai và nhiều xâu ghép có thể giống nhau, khi đó chỉ đếm một lần. VÍ dụ,nếu có 2 xâu cơ bản là x và xx, thì ta thu được xxx từ việc nối x với xx và xx nối x. Tuy nhiên, chúng ta chỉ tính là có một xâu xxx.
Ngoài ra, nếu một xâu xuất hiện nhiều lên trong 1 xâu khác và các vị trí này có thể giao nhau, ta vẫn đếm. Ví dụ, xâu xxx nằm trong xâu xxxx tại 2 vị trí khác nhau và kết quả là 2 mặc dù chúng giao nhau.
Input
Gồm một số test, định dạng mỗi test như sau:
n m e1 e2 . . . en t1 t2 . . . tm
n là số xâu cơ bản, m là số dòng biểu diễn văn bản, 1<=n<=12. Mỗi dòng trong n dòng tiếp theo là 1 xâu cơ bản. Độ dài mẫu xâu cơ bản >=1 và <= 20. m dòng tiếp theo mô tả văn bản.
Văn bản được chia ra làm m dòng nhưng các kí tự xuống dòng không được tính là nằm trong văn bản
Độ dài mỗi dòng >=1 và <=100
Độ dài của đoạn văn bản >=1 và <=5000. Xâu cơ bản và đoạn văn bản chỉ gồm kí tự thường.
Kết thúc bộ test là dòng gồm 2 số 0.
SAMPLE INPUT 3 1 aa b ccc aabccczbaacccbaazaabbcccaa 3 1 a b c cbbcbcbabaacabccaccbaacbccbcaaaccccbcbcbbcacbaacccaccbbcaacbbabbabaccc 3 4 aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 0 0
Output
Với mỗi bộ test, in ra số lần xuất hiện của xâu ghép từ các xâu cơ bản trong văn bản trên 1 dòng.
SAMPLE OUTPUT 5 12 197
- Người up: vdmedragon
- Nguồn bài: Aizu 2008