字符串t和p的长度分别为m和n.t的后缀数组为sa.请说明如何利用t的后缀数组搜索给定字符串p在t中出现的所有位置.要求算法在最坏情况下的时间复杂性为O（mlogn).

查看答案

如果结果不匹配，请联系老师获取答案

您可能会需要：

重置密码查看订单联系客服

安装优题宝APP，拍照搜题省时又省心！

更多“字符串t和p的长度分别为m和n.t的后缀数组为sa.请说明如…”相关的问题

第1题

设主串t和模式串p分别是由d（d≥2)元字符集中随机字符组成的长度为n和m的字符串.试证明简单子串

设主串t和模式串p分别是由d(d≥2)元字符集设主串t和模式串p分别是由d（d≥2)元字符集中随机字符组成的长度为n和m的字符串.试证明简单子串设中随机字符组成的长度为n和m的字符串.试证明简单子串搜索算法所做比较次数的期望值为

设主串t和模式串p分别是由d（d≥2)元字符集中随机字符组成的长度为n和m的字符串.试证明简单子串设

由此可见,对于随机选取的字符串,简单子串搜索算法还是十分有效的.

点击查看答案

第2题

在字符串集合P的AC自动机T中,状态结点s所表示的字符串是从根结点到s的路径上各边的字符依次连接组成的字符串a（s).设s和t是T中两个结点,且u=a（s),v=a（t).试证明,f（s)=t当且仅当v是字符串pi（0≤i＜k)的所有前缀中u的最长真后缀.

点击查看答案

第3题

在模式枚举（pattern enumeration)类应用中，需要从主串T中找出所有的模式串P（T|=n，|P|=m)，而且

在模式枚举(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)试针对这一缺陷改进好后缀策略，使之即便在采用后一约定时，最坏情况下也只需线性时间。

点击查看答案

第4题

问题描述:基因序列是用字符串表示的携带基因信息的DNA分子的一级结构.基因序列的字符集是Σ={A,

问题描述:基因序列是用字符串表示的携带基因信息的DNA分子的一级结构.基因序

列的字符集是Σ={A,C,G,T}.其中字符分别代表组成DNA的4种核苷酸:腺嘌呤、胞嘧啶、鸟嘌呤、胸腺嘧啶.许多疾病往往是由基因突变引起的.这种基因突变是从一个正常的基因序列通过几代人的遗传而产生的.对于基因片段的分析有助于了解基因突变导致的遗传疾病.例如,如果一个基因序列中含有基因片段ATG,则可能含有某种遗传疾病.生物科学家们已经发现许多这类基因片段.对于已知的不安全的基因片段集合P,如果一个基因序列中含有P中基因片段,则称该基因序列为不安全的基因序列,否则称该基因序列为安全的基因序列.

算法设计:对于给定的不安全的基因片段集合P和一个正整数n,计算长度为n的安全的基因序列个数.

数据输入:由文件input.txt提供输入数据.文件的第1行有两个正整数n(1≤n≤2x10⁹)和m(0≤m≤10).n是基因序列长度,m是不安全的基因片段个数.接下来的m行中,每行是一个长度不超过10的不安全的基因片段.每个文件可能有多个测试数据.

结果输出:将计算出的长度为n的安全的基因序列个数mod100000,输出到文件output.txt中.

问题描述:基因序列是用字符串表示的携带基因信息的DNA分子的一级结构.基因序列的字符集是Σ={A,问