阿里测试开发笔试题2020/09/11 （查找敏感词， 图像去噪）

**

阿里测试开发笔试题2020/09/11

**
两道编程题，1个小时， 牛客平台
需要自己编写程序处理输入的字符，并输出结果
**

1. 查找敏感词，输出敏感词在主串中出现的总次数

**
第一行输入两个字符n,m，n代表主字符串长度，m代表将要给出的敏感词数量
第二行给出主字符串
第三行给出敏感词字符串
第四行给出敏感词字符串
…

输入样例1：
10 3
helloworld
hello
world
owo
输出：
3
解释：“hello”、‘world’、"owo"在"helloworld"中各出现1次
输入样例2：
7 3
owowowo
owo
wo
输出：
6
解释："owo"在“owowowo”中出现了3次，“wo”出现了3次，所以敏感词一共出现了6次

个人理解：
就是字符串匹配问题，第二行为主串，第三行及以下为模式串，题目要求模式串在主串中一共出现多少次

第一步，实现对输入、输出的处理：

def main():res = 0  #敏感词出现次数n,m = list(map(int, input().split()))tt = input() #主字符串for i in range(m): line_s = input() #每一行的输入都看作是一个模式串res += kmp_match(tt,line_s)  #利用kmp算法查找字符串return res

第二步，解决“模式串是否在主串中”：
字符串匹配问题可用KMP算法解决：（关于KMP算法可另行查阅资料）

def get_pnext(p):i,k, m = 0, -1, len(p)pnext = [-1] * mwhile i < m -1:if k == -1 or p[i] == p[k]:i += 1k += 1if p[i] == p[k]:pnext[i] = pnext[k]else:pnext[i] = kelse:k = pnext[k]return pnextdef kmp_match(t,p):i,j = 0,0n,m = len(t),len(p)ppnext = get_pnext(p)while i < n and j < m:if j == -1 or t[i] == p[j]:i += 1j += 1else:j = ppnext[j]if j == m: #匹配完模式串的最后一位了，说明模式串在主串中，返回1return 1return 0 #没有找到模式串，返回0

第三步，解决“当前模式串在主串中出现了多少次”
从第二步的kmp_match()中可以看到，当在主串中匹配到模式串时，函数就直接返回1，并不查看主串中后续的字符串中是否还存在模式串。如主串为“owowowo”，模式串为“owo"，从主串的左边开始匹配时，找到第一个“owo”时，kmp_match()就停止查找，并返回1了
所以要看模式串在主串中出现了多少次，就应该在查找到1次后继续查找，直到查找到主串结束
为此，kmp_match()可修改为：

def kmp_match(t,p):ans = 0 #记录当前模式串在主串中出现的次数i,j = 0,0n,m = len(t),len(p)ppnext = get_pnext(p)while i < n: #直到遍历完主串才结束while i < n and j < m:if j == -1 or t[i] == p[j]:i+= 1j += 1else:j = ppnext[j]#如果在主串中匹配到模式串，ans + 1,并将主串指针移到匹配成功的位置的下一个字符处，同时，模式串指针移到下标0处if j == m: ans += 1i = i - j +2j  = 0return ans #返回模式串在主串中出现的次数

完整代码：

def get_pnext(p):i,k, m = 0, -1, len(p)pnext = [-1] * mwhile i < m -1:if k == -1 or p[i] == p[k]:i += 1k += 1if p[i] == p[k]:pnext[i] = pnext[k]else:pnext[i] = kelse:k = pnext[k]return pnextdef kmp_match(t,p):ans = 0i,j = 0,0n,m = len(t),len(p)ppnext = get_pnext(p)while i < n:while i < n and j < m:if j == -1 or t[i] == p[j]:i+= 1j += 1else:j = ppnext[j]if j == m:ans += 1i = i - j +2j  = 0return ansdef main():res = 0 n,m = list(map(int, input().split()))tt = input()for i in range(m):line_s = input()res += kmp_match(tt,line_s)return res

**

2. 图像去噪

**
类似力抠扫雷游戏和图像渲染的结合体， 没大记住，时间基本全用在第一题上了。