東京大学 情報理工学系研究科 コンピュータ科学専攻 2019年8月実施 専門科目I 問題3

Author

zephyr

Description

In this problem, the length of a string is written , and the -th character of is written , where the first character is . The string obtained by removing the first characters from is written . We assume in and . For example, if , then and . The set of characters consists of characters, where is an integer constant no less than 2, and for each character a distinct positive integer is defined. Suppose that the computation of for given and , and that of for given , take time. Also suppose that each of integer addition, multiplication and remainder takes time, and that overflow will never occur in integer operations.

We consider the following problem FIND: For given strings and , find the first position at which matches . In other words, is the least non-negative integer that satisfies

In case there is no such , we define . In the following, we assume .

For strings and with , let function return 1 if the first characters of equal , and return 0 otherwise. Suppose that the time complexity of is . The following algorithm solves the problem FIND:

for (i = 0; i <= l(s) - l(p); i++)
  if (eq(s + i, p) == 1)
    return i;
return -1;

Answer the following questions.

(1) Express the order of the worst-case time complexity of algorithm in terms of and .

In the following, the hash value of the first characters of string is defined by

where and are positive integer constants, and is assumed.

(2) Assume that holds, and that and have been precomputed. Show an algorithm or an expression to compute in time.

(3) Give an algorithm that finds the least non-negative integer that satisfies (but answers if no such exists) in time . Also, answer in what condition the algorithm outputs a value which is not the solution of problem FIND.

(4) Give an algorithm that satisfies all of the following conditions: (a) it always answers the solution of problem FIND, (b) it searches for the answer by using hash and function , and () if we assume that the number of integers that satisfy for given and is independently of and , then the algorithm runs in time . In addition, show in what condition the time complexity of the algorithm is larger than . Also, answer the order of the worst-case time complexity of the algorithm in terms of and .

Kai

(1)

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

Thus, the total time complexity of Algorithm is:

(2)

To compute in time, we can use the rolling hash technique:

Explanation:

• We remove the contribution of from .
• We multiply the result by to shift all values left.
• We add the contribution of the new character .
• We take the modulo to keep the hash value in the correct range.

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

(3)

Algorithm :

1. Precompute .
2. Precompute and check if it matches . If it matches, return 0.
3. For to :
   • Compute from using the formula derived in Q2.
   • If matches , return .

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 is since we are computing the hash values in constant time for each position and there are positions.

Condition when does not give the correct solution: The algorithm 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.

(4)

Algorithm :

1. Precompute .
2. For to :
   • Compute .
   • If , then check eq(s + i, p). If eq(s + i, p) == 1, return .

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: if the first occurrence matches.
• Average Case: If the number of hash matches (that require further checking with eq) is , then the average case time complexity is .
• Worst Case: The worst-case complexity can be if there are many hash collisions, causing frequent calls to eq.

Condition for : The time complexity will be if the expected number of hash collisions is . 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 is when there are many hash collisions, leading to frequent evaluations of eq.

Knowledge

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

难点思路

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

解题技巧和信息

1. 哈希算法: 使用适当的哈希函数和模数 来降低哈希碰撞的概率。
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".