题目内容
（请给出正确答案）
[主观题]
设字符串t和p的长度分别为m和n.t的后缀数组和最长公共前缀数组分别为sa和lcp.请说明如何利用t的后缀数组和最长公共前缀数组搜索给定字符串p在t中出现的所有位置.要求算法在最坏情况下的时间复杂性为O（m+logn).
提问人：网友18***590
发布时间：2022-01-07
如搜索结果不匹配，请 
题目内容
（请给出正确答案）
您可能会需要：
安装简答题APP，拍照搜题省时又省心！
更多“设字符串t和p的长度分别为m和n.t的后缀数组和最长公共前缀…”相关的问题
第1题
设字符串t的后缀数组和最长公共前缀数组分别为sa和lcp.对于非负整数0≤I≤r,t的后缀St和Sr的最长前缀的长度为lce(l,r).设x=sa-1[l],z=sa-1[r],则sa[x]=I,sa[z]=r.不失一般性,可设x<z.试证明lce(l,r)具有如下性质.
点击查看答案
第3题
问题描述:给定2个长度分别为n和m的序列x[0...n-1]和y[0...m-1],以及一个长度为p的约束字符串S[0...p-1].带有子串包含约束的最长公共子序列问题就是要找出x和y的包含s为其子串的最长公共子序列.例如,如果给定的序列x和y分别为AATGCCTAGGC和CGATCTGGAC,字符串s=GTA时,子序列ATCTGGC是x和y的一个无约束的最长公共子序列,而包含s为其子串的最长公共子序列是GTAC.
点击查看答案
算法设计:设计一个算法,找出给定序列x和y的包含s为其子串的最长公共子序列.
数据输入:由文件input.txt提供输入数据.文件的第1行中给出正整数,分别表示给定序列x、y和约束字符串s的长度.接下来的3行分别给出序列x、y和约束字符串s.
结果输出:将计算出的x和y的包含s为其子串的最长公共子序列的长度输出到文件output.txt中.
第4题
问题描述:给定2个长度分别为n和m的序列x[0...n-1]和y[0...m-1],以及d个约束字符串 多子串排
问题描述:给定2个长度分别为n和m的序列x[0...n-1]和y[0...m-1],以及d个约束字符串
多子串排斥约束的最长公共子序列问题就是要找出x和y的不含为其子串的最长公共子序列
点击查看答案
多子串排斥约束的最长公共子序列问题就是要找出x和y的不含为其子串的最长公共子序列算法设计:设计一个算法,找出给定序列x和y的不含为其子串的最长公共子序列.
数据输入:重文件input.txt提供输入数据.文件的第1行中给出正整数d,表示约束字符串个数.接下来的2行分别给出序列x和y.最后d行的每行给出一个约束字符串.
结果输出:将计算出的x和y的不含为其子串的最长公共子序列输出到文件output.txt中.文件的第1行输出最长公共子序列.第2行输出最长公共子序列的长度.
第5题
用动态规划算法求解[图]和[图]的一个最长公共子序列（L...
用动态规划算法求解
和
的一个最长公共子序列（LCS），标记函数的表B[i,j]如下表所示：
该实例的解是(顺序从前到后给出最长公共子序列的字符,字符之间不要加任何符号)
第7题
问题描述:最长公共子序列问题是生物信息学中序列比对问题的一个特例.这类问题在分子生物学和模式识别中有广泛应用.其中最主要的应用是测量基因序列的相似性.在演化分子生物学的研究中发现,某个重要的DNA序列片段常出现在不同的物种中.在测量基因序列的相似性时,如果需要特别关注一个具体的DNA序列片段,就要考察带有子串排斥约束的最长公共子序列问题.这个问题可以具体表述如下.
点击查看答案
给定两个长度分别为n和m的序列x[0...n-1|]和y[0...m-1],以及一个长度为p的约束字符串s[0...p-1].带有子串排斥约束的最长公共子序列问题就是要找出x和y的不包含s为其子串的最长公共子序列.例如,如果给定的序列x和y分别为AATGCCTAGGC和CGATCTGGAC.字符串s=TG时,子序列ATCTGGC是x和y的一个无约束的最长公共子序列,而不包含s为其子串的最长公共子序列是ATCGGC.
算法设计:设计一个算法,找出给定序列x和y的不包含s为其子串的最长公共子序列.
数据输入:由文件input.txt提供输入数据.文件的第1行中给出正整数,分别表示给定序列x和y及约束字符串s的长度.接下来的3行分别给出序列x、y和约束字符串s.
结果输出:将计算出的x和y的不包含s为其子串的最长公共子序列的长度输出到文件output.txt中.
第8题
求一组整数的最大值和最小值。要求：编写函数void Input(int a[])实现一组整数的输入，编写函数int Maxmin(int a[],int *pmax,int *pmin)实现求一组整数的最大值和最小值。
