题目描述：
设计算法，接收字符流，并检查这些字符的后缀是否是字符串数组 words中的一个字符串。
数据范围：
$ 1\le words \le 2000,1\le words[i]\le 200 $
最多调用查询 $ 4\times 10^4 $ 次。
题解：
解法一：trie 树
将 words 中的字符串反转，然后插入trie中，每次接收一个字符之后，反向在 trie 树中查找该字符串前缀，如果存在返回 True，否则返回 False。
解法二：AC自动机
使用AC自动机建立字典图，因为AC自动机查找的时候不匹配会查找最长的后缀。
建立字典图，然后从树根开始，每次接收一个字符就移动，如果存在该字符串，返回 True，否则就跳到 Fail 指针，一直跳。
注意，可能需要使用指针来减少空间的使用。
代码：
解法一：
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
| struct Trie
{
static const int M = 26;
const static int maxn = (2 + 10) * M;
int nex[maxn][M], cnt = 0, val[maxn];
bool exist[maxn];
void ins(string s)
{
int now = 0, len = s.length();
for (int i = 0; i < len; i++)
{
int c = s[i] - 'a';
if (!nex[now][c])
nex[now][c] = ++cnt;
now = nex[now][c];
++val[now];
}
exist[now] = 1;
}
bool find(string &s)
{
int now = 0;
for (int i = s.size() - 1; i >= 0 && s.size() - i <= 200; i--)
{
int c = s[i] - 'a';
if (!nex[now][c])
return false;
now = nex[now][c];
if (exist[now])
return true;
}
}
};
class StreamChecker
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
string s;
Trie tree;
StreamChecker(vector<string> &words)
{
for (int i = 0; i < words.size(); ++i)
{
reverse(words[i].begin(), words[i].end());
tree.ins(words[i]);
}
}
bool query(char letter)
{
s.push_back(letter);
return tree.find(s);
}
};
|
解法二：
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| class StreamChecker
{
const static int M = 26;
const static int maxn = 3e4 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
struct ACTrie
{
int next[maxn][M] = {}, cnt = 0, fail[maxn] = {};
bool exist[maxn] = {};
queue<int> q;
int root;
void insert(string s)
{
int now = 0, len = s.length();
for (int i = 0; i < len; ++i)
{
if (!next[now][s[i] - 'a'])
next[now][s[i] - 'a'] = ++cnt;
now = next[now][s[i] - 'a'];
}
exist[now] = true;
}
void build()
{
for (int i = 0, child; i < M; ++i)
{
child = next[0][i];
if (child)
{
fail[child] = 0;
q.push(child);
}
}
int u, child;
while (q.size())
{
u = q.front();
q.pop();
for (int i = 0; i < M; ++i)
{
child = next[u][i];
if (child)
{
fail[child] = next[fail[u]][i];
q.push(child);
}
else
next[u][i] = next[fail[u]][i];
}
}
root = 0;
}
bool query(char ch)
{
root = next[root][ch - 'a'];
if (exist[root])
return true;
int tmp = root;
while (tmp != 0)
{
tmp = fail[tmp];
if (exist[tmp])
{
return true;
}
}
return false;
}
} trie;
public:
StreamChecker(vector<string> &words)
{
for (int i = 0; i < words.size(); ++i)
{
trie.insert(words[i]);
}
trie.build();
}
bool query(char letter)
{
return trie.query(letter);
}
};
|
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
| struct TrieNode
{
vector<TrieNode *> children;
TrieNode *fail;
bool exist;
TrieNode()
{
children = vector<TrieNode *>(26, nullptr);
fail = nullptr;
exist = false;
}
};
class StreamChecker
{
const static int maxn = 2e3 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
const static int M = 26;
TrieNode *root, *tmp;
void insert(string s)
{
TrieNode *cur = root;
for (int i = 0; i < s.length(); ++i)
{
if (cur->children[s[i] - 'a'] == nullptr)
{
cur->children[s[i] - 'a'] = new TrieNode();
}
cur = cur->children[s[i] - 'a'];
}
cur->exist = true;
}
queue<TrieNode *> q;
void build()
{
root->fail = root;
for (int i = 0; i < M; ++i)
{
if (root->children[i] != nullptr)
{
root->children[i]->fail = root;
q.push(root->children[i]);
}
else root->children[i] = root;
}
while (q.size())
{
TrieNode *u = q.front();
q.pop();
u->exist = u->exist || u->fail->exist;
for (int i = 0; i < M; ++i)
{
if (u->children[i] != nullptr)
{
u->children[i]->fail = u->fail->children[i];
q.push(u->children[i]);
}
else
{
u->children[i] = u->fail->children[i];
}
}
}
tmp = root;
}
public:
StreamChecker(vector<string> &words)
{
root = new TrieNode();
for (int i = 0; i < words.size(); ++i)
{
insert(words[i]);
}
build();
}
bool query(char ch)
{
tmp = tmp->children[ch - 'a'];
if (tmp->exist)
{
return true;
}
else
{
TrieNode *cur = tmp;
while (cur != root && cur)
{
cur = cur->fail;
if (cur->exist)
{
return true;
}
}
return false;
}
}
};
|