题目内容
（请给出正确答案）
[主观题]
设主串t和模式串p分别是由d（d≥2)元字符集中随机字符组成的长度为n和m的字符串.试证明简单子串
设主串t和模式串p分别是由d(d≥2)元字符集
中随机字符组成的长度为n和m的字符串.试证明简单子串搜索算法所做比较次数的期望值为
由此可见,对于随机选取的字符串,简单子串搜索算法还是十分有效的.
答案
查看答案
重要提示：请勿将账号共享给其他人使用，违者账号将被封禁！
查看《购买须知》>>>
请输入或粘贴题目内容
搜题
拍照、语音搜题，请扫码下载APP
题目内容
（请给出正确答案）
设主串t和模式串p分别是由d(d≥2)元字符集中随机字符组成的长度为n和m的字符串.试证明简单子串搜索算法所做比较次数的期望值为
由此可见,对于随机选取的字符串,简单子串搜索算法还是十分有效的.
答案
更多“设主串t和模式串p分别是由d（d≥2)元字符集中随机字符组成的长度为n和m的字符串.试证明简单子串”相关的问题
第1题
第2题
在模式枚举(pattern enumeration)类应用中，需要从主串T中找出所有的模式串P(T|=n，|P|=m)，而且有时允许模式串的两次出现位置之间相距不足m个字符。
类似于教材310页图11.3中的实例，比如在“000000”中查找“000”。若限制多次出现的模式串之间至少相距|P|=3个字符，则应找到2处匹配;反之，若不作限制，则将找到4处匹配。
a)试举例说明，若采用后一约定，则教材11.4.3节BM算法的好后缀策略，可能需要Ω(nm)时间;
b)试针对这一缺陷改进好后缀策略，使之即便在采用后一约定时，最坏情况下也只需线性时间。
第3题
在图9-2(a)中匹配失败后,按前缀函数指示继续作了图(b)~(d)的比较后,最后在图(e)找到一个匹配.事实上,图(b)~(d)的比较都是多余的.因为模式串在位置0、1、2处的字符和位置3处的字符都相等,因此不需要再和主串中位置3处的字符比较,而可以将模式一次向右滑动4个字符,直接进入图(e)的比较.这就是说,在KMP算法中遇到p[j+1]≠t[i],且p[j+1]=p[next[j]+1]时,可一次向右滑动j-next[next[j]]个字符,而不是j-next[j]个字符.根据此观察,设计一个改进的前缀函数,使得遇到上述特殊情况时效率更高.
第6题
假设允许模式串p中可以出现能与任意字符串(包括长度为0的空串)匹配的回隙字符 ,如模式串ab
bac可在主串cabccbacbacab中产生如图9-3所示的匹配.间隙字符可在模式串中出现任意多次,但不允许在主串中出现.
试设计一个多项式时间算法,确定在主串中能否找到与模式串p匹配的子串,并分析算法的计算时间复杂性.
第7题
第8题
A.2 A 12 V
B.2 A 6 V
C.6 A 12 V
D.0.5 A 3 V
第9题
信号xp(t)是对一个频率等于采样频率ωp一半的正弦信号x(t)进行冲激串采样得到的，即
(a) 求一个g(t)， 使得有
(b)证明g(nT)=0，n =0，±1， ±2，...
(c)利用前两部分的结果证明：若xp(t)作为输入加到截止频率为ωs/2的理想低通滤波器上，则其输出为
