NKSEV - Tách từ
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
#include <cstdio>
using namespace std;
struct Trie {
bool last;
Trie * n[26];
};
Trie container[800000];
int ncon;
int n, N;
char a[300030], tmp[444];
Trie root;
int f[300030];
const int mod = 1337377;
void add( char * a) {
Trie * p = &root;
for(int i=0;a[i]!=0;++i) {
int t = a[i] - 'a';
if(p->n[t]!=NULL) p = p->n[t];
else {
p->n[t] = container + ++ncon;
p = p->n[t];
}
}
p->last = true;
}
int main() {
gets(a);
n = strlen(a);
scanf("%d", &N);
gets(tmp);
for(int i=0;i<N;++i) {
gets(tmp);
add( tmp);
}
f[n] = 1;
for(int i=n-1;i>=0;--i) {
Trie * p = &root;
for(int j=i;j<n;++j) {
int t = a[j] - 'a';
if(p->n[t]==NULL) break;
p = p->n[t];
if(p->last) f[i] += f[j+1];
}
f[i] %= mod;
}
cout << f[0] << endl;
//system("pause");
return 0;
}