Giải bài trực tuyến

English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mconstr

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