题目内容
（请给出正确答案）
提问人：网友18***590
发布时间：2022-01-07
[主观题]
试说明如何对最长公共前缀数组lcp做适当预处理,使得最长公共扩展查询在最坏情况下需要O（1)时间.
简答题官方参考答案
（由简答题聘请的专业题库老师提供的解答）
查看官方参考答案
网友您好，请在下方输入框内输入要搜索的题目：
搜题
题目内容
（请给出正确答案）
简答题官方参考答案
（由简答题聘请的专业题库老师提供的解答）
更多“试说明如何对最长公共前缀数组lcp做适当预处理,使得最长公共扩展查询在最坏情况下需要O（1)时间.”相关的问题
第2题
设字符串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题
设字符串t和p的长度分别为m和n.t的后缀数组和最长公共前缀数组分别为sa和lcp.请说明如何利用t的后缀数组和最长公共前缀数组搜索给定字符串p在t中出现的所有位置.要求算法在最坏情况下的时间复杂性为O(m+logn).
第5题
用动态规划算法求解[图]和[图]的一个最长公共子序列（L...
用动态规划算法求解
和
的一个最长公共子序列（LCS），标记函数的表B[i,j]如下表所示：
该实例的解是(顺序从前到后给出最长公共子序列的字符,字符之间不要加任何符号)
第7题
给定两个大整数u和v,它们分别有m和n位数字,且m≤n.用通常的乘法求uv的值需要O(mn)时间.可以将u和v均看作有n位数字的大整数.用本章介绍的分治法,在O(mlog3)时间内计算iuv的值.当m比n小得多时,用这种方法就显得效率不够高.试设计一个算法,在上述情况下用O(nmlog3/2)时间求出uv的值.
第8题
问题描述:给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数.多重集S中重数最大的元素称为众数.例如,S={1,2,2,2,3,5}.多重集s的众数是2,其重数为3.
点击查看答案
算法设计:对于给定的由n个自然数组成的多重集s,计算s的众数及其重数.
数据输入:输入数据由文件名为input.txt的文本文件提供.文件的第1行为多重集S中元素个数n;在接下来的n行中,每行有一个自然数.
结果输出:将计算结果输出到文件outputxt.输出文件有2行,第1行是众数,第2行是重数.
第9题
问题描述:大于1的正整数n可以分解为例如,当n=12时,有8种不同的分解式:算法设计:对于给定的正
问题描述:大于1的正整数n可以分解为
例如,当n=12时,有8种不同的分解式:
点击查看答案
例如,当n=12时,有8种不同的分解式:
算法设计:对于给定的正整数n,计算n共有多少种不同的分解式.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数n
结果输出:将计算出的不同的分解式数输出到文件output.txt.
