【Leetcode】758. Bold Words in String

正解是AC自动机，参考https://blog.csdn.net/qq_46105170/article/details/128060295。也可以用字符串哈希来做。先求出$A$中所有字符串的哈希值，并且记录一下$A$中最短和最长的字符串长度，再求$s$的哈希数组。接着枚举$s[i]$，看以$s[i]$结尾是否能取到$A$中的字符串，可以直接枚举长度，并且长度从大到小枚举（如果长度大的已经覆盖了，小的就不用继续枚举了）。匹配的过程可以直接比较哈希值。代码如下：

class Solution {
 public:
  using UL = unsigned long;
  string boldWords(vector<string>& ws, string s) {
    UL P = 131;
    int n = s.size();
    vector<UL> ha(n + 1), pow(n + 1);
    pow[0] = 1;
    for (int i = 0; i < n; i++) {
      ha[i + 1] = ha[i] * P + s[i];
      pow[i + 1] = pow[i] * P;
    }

    int M = 1, m = 10;
    unordered_set<UL> st;
    for (auto& w : ws) {
      M = max(M, (int)w.size());
      m = min(m, (int)w.size());
      UL h = 0;
      for (char ch : w) h = h * P + ch;
      st.insert(h);
    }

    vector<bool> mark(s.size());
    for (int i = m - 1; i < n; i++)
      // 只枚举长度在[m, M]的范围
	  for (int j = i - M + 1; j <= i - m + 1; j++) {
        if (j < 0) continue;
        UL h = ha[i + 1] - ha[j] * pow[i - j + 1];
        if (st.count(h)) {
          for (int k = j; k <= i; k++) mark[k] = true;
          break;
        }
      }

    string res;
    for (int i = 0; i < n; i++)
      if (!mark[i]) res += s[i];
      else {
        res += "";
        while (i < n && mark[i]) res += s[i++];
        res += "";
        i--;
      }

    return res;
  }
};
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

时间复杂度$O(\sum l_{A_i}+n\max l_{A_i})$，空间$O(l_A+n)$。