1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include <iostream>
#include <queue>
#include <string>
#include <string_view>
#include <vector>
struct TrieNode {
char c;
size_t d;
bool isend;
std::vector<TrieNode> next;
TrieNode(char x, size_t y) : c{x}, d{y}, isend{false}, next() {}
};
void push(std::string_view s, TrieNode& t) {
if (s.empty()) {
t.isend = true;
return;
}
for (auto& u : t.next) {
if (s[0] == u.c) {
push(s.substr(1), u);
return;
}
}
t.next.push_back(TrieNode(s[0], t.d+1));
push(s.substr(1), t.next.back());
}
const TrieNode* next(const TrieNode* w, char c) {
for (size_t i = 0; i < w->next.size(); i++)
if (w->next[i].c == c)
return &w->next[i];
return nullptr;
}
int f(std::vector<int>& t, std::string_view s, const TrieNode& d, size_t i) {
static constexpr long long mod = 1e9+7;
if (t[i] != -1) return t[i];
t[i] = 0;
for (const TrieNode* w = &d; w != nullptr; w = next(w, s[w->d]))
if (w->isend)
t[i] = (t[i] + f(t, s.substr(w->d), d, i+w->d)) % mod;
return t[i];
}
int main() {
std::string s, u;
size_t k;
std::cin >> s >> k;
TrieNode d('\0', 0);
for (size_t i = 0; i < k; i++) {
std::cin >> u;
push(u, d);
}
std::vector<int> t(s.size()+1, -1);
t[s.size()] = 1;
std::cout << f(t, s, d, 0) << "\n";
}
|
