string text;
vs pattern;
struct trie{
vector< trie* > ch;
trie *sfx;
trie *dict_sfx;
int index;
trie(){
ch.resize( 26 );
for( int i = 0; i < 26; ++i )
ch[ i ] = NULL;
sfx = dict_sfx = NULL;
index = -1;
}
};
void insert( trie *root, const string &s, int pid ){
trie *p = root;
for( int i = 0; i < s.size(); ++i ){
if( p->ch[ s[ i ] - 'A' ] == NULL )
p->ch[ s[ i ] - 'A' ] = new trie();
p = p->ch[ s[ i ] - 'A' ];
}
p->index = pid;
}
void build_sfx_link( trie *root ){
trie *q[ 1000001 ], **qf, **qb;
qf = qb = q;
*qb++ = root;
while( qf < qb ){
trie *p = *qf++;
for( int i = 0; i < 26; ++i )
if( p->ch[ i ] ){
trie *q = p->sfx;
while( q and q->ch[ i ] == NULL )
q = q->sfx;
if( q )
p->ch[ i ]->sfx = q->ch[ i ];
else
p->ch[ i ]->sfx = root;
trie *r = p->ch[ i ]->sfx;
if( r->index != -1 )
p->ch[ i ]->dict_sfx = r;
else
p->ch[ i ]->dict_sfx = r->dict_sfx;
*qb++ = p->ch[ i ];
}
}
}
void match( trie *root, const string &t, vi &occur ){
trie *p = root;
for( int i = 0; i < t.size(); ++i ){
while( p and p->ch[ t[ i ] - 'A' ] == NULL )
p = p->sfx;
if( p )
p = p->ch[ t[ i ] - 'A' ];
else
p = root;
for( trie *q = p; q; q = q->dict_sfx )
if( q->index != -1 )
occur[ i - pattern[ q->index ].size() + 1 ] = 1;
}
}
void solve(){
cin >> text;
int N; cin >> N;
for( int i = 0; i < N; ++i ){
string s; cin >> s;
pattern.push_back( s );
}
trie *root_trie = new trie();
for( int i = 0; i < N; ++i )
insert( root_trie, pattern[ i ], i );
build_sfx_link( root_trie );
vi occur( text.size() );
match( root_trie, text, occur );
vi ans;
for( int i = 0; i < occur.size(); ++i )
if( occur[ i ] )
ans.push_back( i );
for( int i = 0; i < ans.size(); ++i )
cout << ans[ i ] << " \n"[ i + 1 == ans.size() ];
}