NKSEV - Tách từ
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<cstring>
const int N = 4000 + 2, L = 300000 + 2, WL = 100 + 2, MOD = 1337377;
struct TrieNode {
int next[26], nfinish;
} trie[N * WL];
int nnode = 1, n, f[L];
char tmp[WL], s[L];
void insert(const char * s) {
int u = 0;
for(int i = strlen(s) - 1; i >= 0; --i) {
int t = s[i] - 0x61;
if(trie[u].next[t] == 0) trie[u].next[t] = nnode++;
u = trie[u].next[t];
}
trie[u].nfinish = 1;
}
void enter() {
scanf("%s%d", s+1, &n);
for(int i = 0; i < n; ++i) {
scanf("%s", tmp);
insert(tmp);
}
}
void solve() {
f[0] = 1; int l = strlen(s + 1);
for(int i = 1; i <= l; ++i) {
int u = 0;
for(int j = i; j && trie[u].next[s[j] - 0x61]; --j)
if(trie[u = trie[u].next[s[j] - 0x61]].nfinish)
f[i] = (f[j-1] + f[i]) % MOD;
}
printf("%d\n", f[l]);
}
int main() {
enter();
solve();
return 0;
}