#include <iostream>
#include <queue>
#include <string>
using namespace std;
struct Trie {
bool output;
Trie* go[ 96 ] , * fail;
~Trie( ) {
for ( int i= 0 ; i< 96 ; i++ ) if ( go[ i] ) delete go[ i] ;
}
void insert( char * s) {
if ( * s == '\0 ' ) {
output = true ;
return ;
}
int n = * s - 32 ;
if ( ! go[ n] ) go[ n] = new Trie( ) ;
go[ n] - > insert( s+ 1 ) ;
}
} ;
void BFS( Trie* root) {
queue< Trie* > Q;
root- > fail = root; Q.push ( root) ;
while ( ! Q.empty ( ) ) {
Trie* cur = Q.front ( ) ; Q.pop ( ) ;
for ( int i= 0 ; i< 96 ; i++ ) {
Trie* next = cur- > go[ i] ;
if ( ! next) continue ;
if ( cur == root) next- > fail = root;
else {
Trie* dest = cur- > fail;
while ( dest ! = root && ! dest- > go[ i] )
dest = dest- > fail;
if ( dest- > go[ i] ) dest = dest- > go[ i] ;
next- > fail = dest;
}
if ( next- > fail- > output) next- > output = true ;
Q.push ( next) ;
}
}
}
int find( string s, Trie* root) {
int ret = 0 ;
Trie* cur = root;
for ( int i= 0 ; s[ i] ; i++ ) {
int n = s[ i] - 32 ;
while ( cur ! = root && ! cur- > go[ n] )
cur = cur- > fail;
if ( cur- > go[ n] ) cur = cur- > go[ n] ;
if ( cur- > output) {
++ ret;
cur = root;
}
}
return ret;
}
int main( )
{
ios_base:: sync_with_stdio ( false ) ; cin .tie ( 0 ) ; cout .tie ( 0 ) ;
int N, M; char str[ 81 ] ;
while ( true ) {
cin >> N >> M;
if ( N == 0 ) break ;
Trie* root = new Trie( ) ;
while ( N-- ) {
cin >> str;
root- > insert( str) ;
}
BFS( root) ;
string S; getline( cin , S) ;
int ans = 0 ;
while ( M-- ) {
getline( cin ,S) ;
ans + = find( S, root) ;
}
cout << ans << "\n " ;
delete root;
}
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxzdHJpbmc+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3QgVHJpZSB7Cglib29sIG91dHB1dDsKCVRyaWUqIGdvWzk2XSwgKmZhaWw7CgkKCX5UcmllKCkgewoJCWZvcihpbnQgaT0wOyBpPDk2OyBpKyspIGlmIChnb1tpXSkgZGVsZXRlIGdvW2ldOwoJfQoJCgl2b2lkIGluc2VydChjaGFyKiBzKSB7CgkJaWYgKCpzID09ICdcMCcpIHsKCQkJb3V0cHV0ID0gdHJ1ZTsKCQkJcmV0dXJuOwoJCX0KCQkKCQlpbnQgbiA9ICpzIC0gMzI7CgkJaWYgKCFnb1tuXSkgZ29bbl0gPSBuZXcgVHJpZSgpOwoJCWdvW25dLT5pbnNlcnQocysxKTsKCX0KfTsKCnZvaWQgQkZTKFRyaWUqIHJvb3QpIHsKCXF1ZXVlPFRyaWUqPiBROwoJcm9vdC0+ZmFpbCA9IHJvb3Q7IFEucHVzaChyb290KTsKCXdoaWxlICghUS5lbXB0eSgpKSB7CgkJVHJpZSogY3VyID0gUS5mcm9udCgpOyBRLnBvcCgpOwoJCWZvcihpbnQgaT0wOyBpPDk2OyBpKyspIHsKCQkJVHJpZSogbmV4dCA9IGN1ci0+Z29baV07CgkJCWlmICghbmV4dCkgY29udGludWU7CgkJCQoJCQlpZiAoY3VyID09IHJvb3QpIG5leHQtPmZhaWwgPSByb290OwoJCQllbHNlIHsKCQkJCVRyaWUqIGRlc3QgPSBjdXItPmZhaWw7CgkJCQl3aGlsZSAoZGVzdCAhPSByb290ICYmICFkZXN0LT5nb1tpXSkKCQkJCQlkZXN0ID0gZGVzdC0+ZmFpbDsKCQkJCWlmIChkZXN0LT5nb1tpXSkgZGVzdCA9IGRlc3QtPmdvW2ldOwoJCQkJbmV4dC0+ZmFpbCA9IGRlc3Q7CgkJCX0KCQkJCgkJCWlmIChuZXh0LT5mYWlsLT5vdXRwdXQpIG5leHQtPm91dHB1dCA9IHRydWU7CgkJCVEucHVzaChuZXh0KTsKCQl9Cgl9Cn0KCmludCBmaW5kKHN0cmluZyBzLCBUcmllKiByb290KSB7CglpbnQgcmV0ID0gMDsKCVRyaWUqIGN1ciA9IHJvb3Q7Cglmb3IoaW50IGk9MDsgc1tpXTsgaSsrKSB7CgkJaW50IG4gPSBzW2ldIC0gMzI7CgkJd2hpbGUgKGN1ciAhPSByb290ICYmICFjdXItPmdvW25dKQoJCQljdXIgPSBjdXItPmZhaWw7CgkJaWYgKGN1ci0+Z29bbl0pIGN1ciA9IGN1ci0+Z29bbl07CgkJCgkJaWYgKGN1ci0+b3V0cHV0KSB7CgkJCSsrcmV0OwoJCQljdXIgPSByb290OwoJCX0KCX0KCXJldHVybiByZXQ7Cn0KCmludCBtYWluKCkKewoJaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7IGNpbi50aWUoMCk7IGNvdXQudGllKDApOwoJaW50IE4sIE07IGNoYXIgc3RyWzgxXTsKCQoJd2hpbGUgKHRydWUpIHsKCQljaW4gPj4gTiA+PiBNOwoJCWlmIChOID09IDApIGJyZWFrOwoJCQoJCVRyaWUqIHJvb3QgPSBuZXcgVHJpZSgpOwoJCXdoaWxlIChOLS0pIHsKCQkJY2luID4+IHN0cjsKCQkJcm9vdC0+aW5zZXJ0KHN0cik7CgkJfQoJCUJGUyhyb290KTsKCQkKCQlzdHJpbmcgUzsgZ2V0bGluZShjaW4sIFMpOwoJCWludCBhbnMgPSAwOwoJCXdoaWxlIChNLS0pIHsKCQkJZ2V0bGluZShjaW4gLFMpOwoJCQlhbnMgKz0gZmluZChTLCByb290KTsKCQl9CgkJY291dCA8PCBhbnMgPDwgIlxuIjsKCQkKCQlkZWxldGUgcm9vdDsKCX0KfQ==
stdin
NCA2CjotKQo6LSgKKC06CiktOgpIZWxsbyB1bmNsZSBKb2huISA6LSkgOi1ECkkgYW0gc2FkIG9yIGhhcHB5PyAoLTotKD8KSSBmZWVsIHNvIGhhcHB5LCBteSBoZWFkIHNwaW5zCigtOi0pKC06LSkoLTotKSgtOi0pIDotKSAoLTogOi0pCmJ1dCB0aGVuIHNhZG5lc3MgY29tZXMgOi0oCkxvdmVzIHlvdSwgSm9hbm5hIDotKSkpKSkKMyAxCjopCik6CikpCjopOikpOikpOikpOig6KCg6KCgoOik6KQowIDA=
4 6
:-)
:-(
(-:
)-:
Hello uncle John! :-) :-D
I am sad or happy? (-:-(?
I feel so happy, my head spins
(-:-)(-:-)(-:-)(-:-) :-) (-: :-)
but then sadness comes :-(
Loves you, Joanna :-)))))
3 1
:)
):
))
:):)):)):)):(:((:(((:):)
0 0