IS CS-2020S1-03

题目来源：Problem 3 日期：2024-08-07 题目主题：CS-算法-字符串匹配

解题思路

此题探讨字符串匹配问题中的几种算法及其复杂度分析。我们需要讨论暴力搜索算法 $S$ 的时间复杂度，以及基于哈希值计算的优化算法。我们还要设计一种结合哈希值和字符串比较的算法 $H$ 来确保找到字符串的匹配位置。

Solution

Q1: Time Complexity of Algorithm $S$

Algorithm $S$ iterates over all possible starting positions in the string $s$ to check if the substring of $s$ starting at position $i$ matches the pattern $p$. For each starting position, the function eq(s + i, p) is called, which has a time complexity of $O(\ell (p))$.

Thus, the total time complexity of Algorithm $S$ is:

$$O((\ell (s)-\ell (p)+1)\cdot \ell (p))=O(\ell (s)\cdot \ell (p))$$

Q2: Computing $h(s+i+1,m)$

To compute $h(s+i+1,m)$ in $O(1)$ time, we can use the rolling hash technique:

$h(s+i+1,m)=((h^{\prime }-\text{numval}(s[i])\cdot d_m)\cdot d+\text{numval}(s[i+m]))\mathrm{mod}q$

Explanation:

• We remove the contribution of $s[i]$ from $h^{\prime }$.
• We multiply the result by $d$ to shift all values left.
• We add the contribution of the new character $s[i+m]$.
• We take the modulo $q$ to keep the hash value in the correct range.

This computation can be done in $O(1)$ time as all operations (subtraction, multiplication, addition, and modulo) are assumed to take constant time.

Q3: Algorithm $H_0$

Algorithm $H_0$:

1. Precompute $h(p,\ell (p))$.
2. Precompute $h(s,\ell (p))$ and check if it matches $h(p,\ell (p))$. If it matches, return 0.
3. For $i=1$ to $\ell (s)-\ell (p)$:
   • Compute $h(s+i,\ell (p))$ from $h(s+i-1,\ell (p))$ using the formula derived in Q2.
   • If $h(s+i,\ell (p))$ matches $h(p,\ell (p))$, return $i$.

int H_0(string s, string p) {
  int lp = ell(p);
  int ls = ell(s);
  int hp = h(p, lp);
  int hs = h(s, lp);
 
  if (hp == hs) return 0;
 
  for (int i = 1; i <= ls - lp; i++) {
    hs = (d * (hs - numval(s[i - 1]) * d_m) + numval(s[i + lp - 1])) % q;
    if (hp == hs) return i;
  }
 
  return -1;
}

The time complexity of $H_0$ is $O(\ell (s)+\ell (p))$ since we are computing the hash values in constant time for each position and there are $O(\ell (s))$ positions.

Condition when $H_0$ does not give the correct solution: The algorithm $H_0$ only checks for hash matches. In the rare case where different strings have the same hash value (hash collision), the algorithm might mistakenly report a false match.

Q4: Algorithm $H$

Algorithm $H$:

1. Precompute $h(p,\ell (p))$.
2. For $i=0$ to $\ell (s)-\ell (p)$:
   • Compute $h(s+i,\ell (p))$.
   • If $h(s+i,\ell (p))=h(p,\ell (p))$, then check eq(s + i, p). If eq(s + i, p) == 1, return $i$.

int H(string s, string p) {
  int lp = ell(p);
  int ls = ell(s);
  int hp = h(p, lp);
  int hs = h(s, lp);
 
  if (hp == hs && eq(s, p) == 1) return 0;
 
  for (int i = 1; i <= ls - lp; i++) {
    hs = (d * (hs - numval(s[i - 1]) * d_m) + numval(s[i + lp - 1])) % q;
    if (hp == hs && eq(s + i, p) == 1) return i;
  }
 
  return -1;
}

Time Complexity:

• Best Case: $O(\ell (p))$ if the first occurrence matches.
• Average Case: If the number of hash matches (that require further checking with eq) is $O(1)$, then the average case time complexity is $O(\ell (s)+\ell (p))$.
• Worst Case: The worst-case complexity can be $O(\ell (s)\cdot \ell (p))$ if there are many hash collisions, causing frequent calls to eq.

Condition for $O(\ell (s)+\ell (p))$: The time complexity will be $O(\ell (s)+\ell (p))$ if the expected number of hash collisions is $O(1)$. In other words, if the hash function has good distribution and the probability of collisions is low, the algorithm runs efficiently.

Worst-case Complexity: The worst-case time complexity of algorithm $H$ is $O(\ell (s)\cdot \ell (p))$ when there are many hash collisions, leading to frequent evaluations of eq.

知识点

字符串匹配哈希算法Rabin-Karp算法复杂度分析

难点思路

此题的难点在于如何高效地计算字符串的哈希值，并利用哈希值进行匹配。在应对哈希碰撞时，我们需要进行字符串的实际比较，保证算法的正确性。

解题技巧和信息

1. 哈希算法: 使用适当的哈希函数和模数 $q$ 来降低哈希碰撞的概率。
2. 滚动哈希: 是一种高效的技术,可以在 O(1) 时间内更新哈希值。
3. 字符串比较: 当哈希值匹配时，需要使用实际的字符串比较来确认结果。
4. 复杂度分析: 分析算法的平均情况和最坏情况的复杂度，以便选择合适的解决方案。

重点词汇

1. Hash Function (哈希函数): A function that maps data of arbitrary size to fixed-size values.
2. Collision (碰撞): When two different inputs produce the same hash output.
3. Rabin-Karp Algorithm (Rabin-Karp 算法): A string matching algorithm that uses hash values for efficient searching.

• string matching 字符串匹配
• rolling hash 滚动哈希
• time complexity 时间复杂度
• worst-case scenario 最坏情况
• hash collision 哈希冲突

参考资料

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd Edition, Chapter 32: “String Matching”.