跳到主要内容

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

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

In this problem, the length of a string ss is written l(s)l(s), and the ii-th character of ss is written s[i]s[i], where the first character is s[0]s[0]. The string obtained by removing the first ii characters from ss is written s+is + i. We assume 0≤i<l(s)0 \leq i < l(s) in s[i]s[i] and s+is + i. For example, if s=PROBLEMs = \text{PROBLEM}, then s[0]=Ps[0] = \text{P} and s+3=BLEMs + 3 = \text{BLEM}. The set of characters consists of NN characters, where NN is an integer constant no less than 2, and for each character cc a distinct positive integer numval(c)≤N\text{numval}(c) \leq N is defined. Suppose that the computation of s+is + i for given ss and ii, and that of numval(c)\text{numval}(c) for given cc, take O(1)O(1) time. Also suppose that each of integer addition, multiplication and remainder takes O(1)O(1) time, and that overflow will never occur in integer operations.

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

∀j∈{0,1,…,l(p)−1}. s[i+j]=p[j].\forall j \in \{0, 1, \dots, l(p) - 1\}. \, s[i + j] = p[j].

In case there is no such ii, we define i=−1i = -1. In the following, we assume l(s)>l(p)>0l(s) > l(p) > 0.

For strings rr and pp with 0<l(p)≤l(r)0 < l(p) \leq l(r), let function eq(r,p)\text{eq}(r, p) return 1 if the first l(p)l(p) characters of rr equal pp, and return 0 otherwise. Suppose that the time complexity of eq(r,p)\text{eq}(r, p) is O(l(p))O(l(p)). The following algorithm SS 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 SS in terms of l(s)l(s) and l(p)l(p).

In the following, the hash value h(s,m)h(s, m) of the first mm characters of string ss is defined by

h(s,m)=(∑i=0m−1numval(s[i])⋅dm−i−1)mod  q,h(s, m) = \left(\sum_{i=0}^{m-1} \text{numval}(s[i]) \cdot d^{m-i-1}\right) \mod q,

where dd and qq are positive integer constants, and 0<m≤l(s)0 < m \leq l(s) is assumed.

(2) Assume that i<l(s)−mi < l(s) - m holds, and that h′=h(s+i,m)h' = h(s + i, m) and dm=dm−1d_m = d^{m-1} have been precomputed. Show an algorithm or an expression to compute h(s+i+1,m)h(s + i + 1, m) in O(1)O(1) time.

(3) Give an algorithm H0H_0 that finds the least non-negative integer ii that satisfies h(p,l(p))=h(s+i,l(p))h(p, l(p)) = h(s + i, l(p)) (but answers −1-1 if no such ii exists) in time O(l(s)+l(p))O(l(s) + l(p)). Also, answer in what condition the algorithm H0H_0 outputs a value which is not the solution of problem FIND.

(4) Give an algorithm HH 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 h(s,m)h(s, m) and function eq(r,p)\text{eq}(r, p), and (cc) if we assume that the number of integers ii that satisfy h(p,l(p))=h(s+i,l(p))h(p, l(p)) = h(s + i, l(p)) for given ss and pp is O(1)O(1) independently of ss and pp, then the algorithm HH runs in time O(l(s)+l(p))O(l(s) + l(p)). In addition, show in what condition the time complexity of the algorithm HH is larger than O(l(s)+l(p))O(l(s) + l(p)). Also, answer the order of the worst-case time complexity of the algorithm HH in terms of l(s)l(s) and l(p)l(p).

题目描述​

字符串 ss 的长度记为 l(s)l(s)，从 00 开始编号的第 ii 个字符记为 s[i]s[i]，删去前 ii 个字符所得后缀记为 s+is+i，并在这些记号中假设 0≤i<l(s)0\le i<l(s)。例如 s=PROBLEMs=\text{PROBLEM} 时， s[0]=Ps[0]=\text P、s+3=BLEMs+3=\text{BLEM}。字符集含常数 N≥2N\ge2 个字符，每个字符 cc 对应互不相同的正整数 numval⁡(c)≤N\operatorname{numval}(c)\le N。假设计算 s+is+i、numval⁡(c)\operatorname{numval}(c)、整数加法、乘法和取余均为 O(1)O(1)，且整数运算不会溢出。

问题 FIND 要求：给定字符串 p,sp,s，求 pp 在 ss 中第一次匹配的起点，即满足

∀j∈{0,…,l(p)−1},s[i+j]=p[j]\forall j\in\{0,\ldots,l(p)-1\},\quad s[i+j]=p[j]

的最小非负整数 ii；若不存在则返回 −1-1。以下假设 l(s)>l(p)>0l(s)>l(p)>0。对满足 0<l(p)≤l(r)0<l(p)\le l(r) 的字符串，函数 eq⁡(r,p)\operatorname{eq}(r,p) 在 rr 的前 l(p)l(p) 个字符等于 pp 时返回 11，否则返回 00，耗时 O(l(p))O(l(p))。题中朴素算法 SS 从左到右对每个位置调用该函数。

（1）用 l(s),l(p)l(s),l(p) 表示算法 SS 的最坏时间复杂度。

对满足 0<m≤l(s)0<m\le l(s) 的 mm，定义前 mm 个字符的哈希：

h(s,m)=(∑i=0m−1numval⁡(s[i])dm−i−1) mod q,h(s,m)= \left(\sum_{i=0}^{m-1} \operatorname{numval}(s[i])d^{m-i-1}\right)\bmod q,

其中 d,qd,q 为正整数常数。

（2）设 i<l(s)−mi<l(s)-m，且已预计算 h′=h(s+i,m)h'=h(s+i,m) 和 dm=dm−1d_m=d^{m-1}。给出在 O(1)O(1) 时间内计算 h(s+i+1,m)h(s+i+1,m) 的算法或表达式。

（3）给出算法 H0H_0，在 O(l(s)+l(p))O(l(s)+l(p)) 时间内找出满足 h(p,l(p))=h(s+i,l(p))h(p,l(p))=h(s+i,l(p)) 的最小非负 ii；若不存在则返回 −1-1。并说明在什么条件下 H0H_0 的输出不是 FIND 的正确答案。

（4）给出算法 HH，满足：始终正确求解 FIND；使用哈希 hh 和函数 eq 搜索；若对给定 s,ps,p，哈希相等的候选位置数与输入无关地为 O(1)O(1)，则总耗时为 O(l(s)+l(p))O(l(s)+l(p))。此外说明何种条件会使其耗时超过这一界，并用 l(s),l(p)l(s),l(p) 给出最坏时间复杂度。

Kai​

记 n=l(s),m=l(p)n=l(s),m=l(p)。

(1)​

共有 n−m+1n-m+1 个起点，每次比较至多 mm 个字符，故最坏时间为

O((n−m+1)m)⊆O(nm).O((n-m+1)m)\subseteq O(nm).

若 eq 采用逐字符比较，取 s=an,p=am−1bs=a^n,p=a^{m-1}b 可达到 Θ((n−m+1)m)\Theta((n-m+1)m)。

(2)​

令 mod⁡q(x)\operatorname{mod}_q(x) 为 0,…,q−10,\ldots,q-1 中的标准余数，则

h(s+i+1,m)=mod⁡q(d(h′−numval⁡(s[i])dm)+numval⁡(s[i+m])).\boxed{h(s+i+1,m)=\operatorname{mod}_q \left(d(h'-\operatorname{numval}(s[i])d_m)+\operatorname{numval}(s[i+m])\right).}

此式删除最左字符的贡献、将其余项乘 dd，再加上新字符，耗时 O(1)O(1)。若语言的 % 会返回负数，使用 ((x % q) + q) % q 实现标准余数。

(3)​

用 Horner 递推 v = mod_q(v*d + numval(c)) 求两个初始哈希，并用 m−1m-1 次乘法求 dmd_m。

hp = h(p,m); hs = h(s,m)
for i = 0,...,n-m:
    if hs == hp: return i
    if i < n-m:
        hs = mod_q(d*(hs-numval(s[i])*d_m)+numval(s[i+m]))
return -1

初始化为 O(m)O(m)，每次滚动为 O(1)O(1)，故共 O(n+m)O(n+m)。

H0H_0 错误当且仅当它找到的第一个哈希相等窗口并不等于 pp。若没有哈希相等窗口，则必无真正匹配，返回 −1-1 正确。

(4)​

将上面算法的返回条件改成

if hs == hp and eq(s+i,p) == 1: return i

便得到 HH。真正相等的串哈希一定相等，且扫描按起点递增进行，因此总能返回首个真正匹配。

设返回前实际检查了 cc 个候选窗口，总时间为

O(n+m+cm).O(n+m+cm).

若 c=O(1)c=O(1)，即为 O(n+m)O(n+m)。当大量碰撞引发长字符比较，使比较总耗时超过线性界时，算法退化。例如允许的常数 q=1q=1 使所有窗口碰撞，取 s=an,p=am−1bs=a^n,p=a^{m-1}b，逐字符 eq 每次都比较 mm 个字符。

因此最坏上界为 O((n−m+1)m)O((n-m+1)m)，逐字符比较下上述例子达到该界；常见宽松写法为 O(nm)O(nm)。仅有许多哈希相等位置并不足以断言退化，因为算法可能很早就返回。

本页目录