1function buildTrie(patterns) {
2 const trie = [{ next: {}, fail: 0, out: [] }];
3 for (const p of patterns) {
4 let cur = 0;
5 for (const ch of p) {
6 if (trie[cur].next[ch] === undefined)
7 trie.push({ next: {}, fail: 0, out: [] }), (trie[cur].next[ch] = trie.length - 1);
8 cur = trie[cur].next[ch];
9 }
10 trie[cur].out.push(p);
11 }
12 return trie;
13}
14function buildFail(trie) {
15 const queue = [0];
16 while (queue.length) {
17 const u = queue.shift();
18 for (const [ch, v] of Object.entries(trie[u].next)) {
19 let f = trie[u].fail;
20 while (f && trie[f].next[ch] === undefined) f = trie[f].fail;
21 trie[v].fail = u === 0 ? 0 : trie[f].next[ch] ?? 0;
22 trie[v].out = trie[v].out.concat(trie[trie[v].fail].out);
23 queue.push(v);
24 }
25 }
26}
27function acMatch(trie, text) {
28 let cur = 0;
29 const res = [];
30 for (let i = 0; i < text.length; i++) {
31 const ch = text[i];
32 while (cur && trie[cur].next[ch] === undefined) cur = trie[cur].fail;
33 if (trie[cur].next[ch] !== undefined) cur = trie[cur].next[ch];
34 for (const p of trie[cur].out) res.push({ pattern: p, end: i });
35 }
36 return res;
37}