Homework 5

标★的题目为选做题，仅供学有余力的同学尝试，并且评分标准也更严格。请先做完不标★的题目，再尝试做标一个★的题目，再尝试做更多★的题目。

• 字符串是啥：7+0.2
• 字符串匹配：21+1.1
• 更多的字符串匹配：4+0.3

本次作业总分：32+1.6

字符串是啥

语言基础（7.2分）

1. scanf函数返回值的意义是？读入的变量的数量
2. printf函数返回值的意义是？输出了多少个变量
3. sscanf函数返回值的意义是？有多少个变量被赋值了
4. sprintf函数返回值的意义是？有多少个变量被输出到Stl
5. strcmp函数返回值的意义是？第二个字符串ascii-第一个字符串ascii
6. strncmp函数返回值的意义是？长度为n的两个字符串后-前
7. strstr函数返回值的意义是？第二个串在第一个串中出现的位置的地址
8. ★strcpy函数返回值的意义是？第一个串的地址
9. ★strncpy函数返回值的意义是？同上，只不过是长度为n的

字符串匹配

哈希（4.1分）

设字符集为小写字母，某个字母对应的整数是其顺序编号加上$a$。例如a对应$a$，b对应$a+1$，c对应$a+2$……

设哈希函数为多项式哈希，乘数为$b$，模数为$c$。例如acc对应$(ab^2+(a+2)b+(a+2)) \bmod c$。

1. 对于$a=0$，找出两个字符串，无论$b,c$为何值，这两个字符串的哈希值都相等。这个故事告诉我们不要用$a=0$。a aaaaaaa
2. 对于$a=1,b=23$，找出两个字符串，无论$c$为何值，这两个字符串的哈希值都相等。这个故事告诉我们不要用$b<26$。``
3. 对于$a=1,b=31,c=313$，找出两个哈希值相等的字符串。
4. 对于$a=233,b=313,c=998244353$，找出两个哈希值相等的字符串。
5. ★★对于$a=1,b=313,c=2^{64}$，找出两个哈希值相等的字符串。

概率（11分）

有$n$个数，每个数等概率取为$[1,10^6]$范围内的整数。对于以下$n$的取值，估算这$n$个数中存在重复数的概率，只需要选取以下选项中的一个：

A. 几乎不可能（概率小于$10^{-5}$）
B. 极小可能（概率至少为$10^{-5}$，但小于$10^{-3}$）
C. 较小可能（概率至少为$10^{-3}$，但小于10%）
D. 可能（概率至少为10%，至多为90%）
E. 较大可能（概率大于90%，但不超过$1-10^{-3}$）
F. 极大可能（概率大于$1-10^{-3}$，但不超过$1-10^{-5}$）
G. 几乎必然（概率大于$1-10^{-5}$）

1. $n=1$ A
2. $n=2$
3. $n=3$
4. $n=10$
5. $n=100$
6. $n=1000$
7. $n=10000$
8. $n=10^5$
9. $n=10^6$
10. $n=10^7$

★★稍微精确地计算上述概率。计算结果保留5位有效数字。

KMP（5分）

假设要对模式串s进行KMP算法的预处理得到next。

设s的长度为n，且字符存放于s[1]到s[n]的位置。设next[i]表示：小于i的最大的非负整数j，使得s的长度为j的前缀等于s的长度为i的前缀的长度为j的后缀的（如果不存在这样的正整数j，则next[i]为0，因为空串和空串总是相等的）。

下面是一个试图完成这项工作的程序：

char s[MAXN];
int n;
// 假定s和n已经被处理好了
int next[MAXN];
memset(next, 0, sizeof(next));
for(int i = 1; i <= n; i++)
{
    int j = next[i - 1];
    while(j && s[j + 1] != s[i])
        j = next[j];
    if(s[j + 1] == s[i])
        next[i] = j + 1;
    else
        next[i] = j;
}

1. 给出一个输入串，使得这个程序能够正常结束，但是得到了错误的结果。
2. 给出一个输入串，使得这个程序会死循环。
3. 改正这个程序。
4. 简要说明一个正确的处理next数组的程序的时间复杂度为$O(n)$。
5. 简要说明，构建完next数组后，对于某个长度为$m$的待匹配串，KMP算法进行匹配的时间复杂度为$O(m)$（注意，不要只说明$O(n+m)$，要说明$O(m)$）。

迷思（2分）

举出两个例子，使得不一定使用哈希或KMP等高级算法，只需用暴力算法就能完成字符串匹配。

更多的字符串匹配

Trie与AC算法（4分）

给定下列字符串：

• abacaba
• ababa
• aba
• aca
• bab
• bac
• acaca

• cab

  1. 建立Trie，画出之。
  2. 建立AC自动机，画出之。
  3. 为什么建立AC自动机时要用BFS，而不用DFS？
  4. 假设字符集大小为常数，则建立AC自动机的时间复杂度为？（无需证明）

★调查问卷（0.3分）

1. 你用了多长时间完成今天的作业？
2. 对于昨天的考试，你的看法如何？
3. 猜猜看今天下发的带答案的材料有什么用？

Written with StackEdit.