首页
设正文串长度为n，模式串长度为m，则模式匹配的KMP算法的时间复杂度为（）。
精华吧
→
答案
→
慕课
→
未分类
设正文串长度为n，模式串长度为m，则模式匹配的KMP算法的时间复杂度为（）。
A.O(m*n)
B.O(m+n)
C.O(m)
D.O(n)
正确答案：O(m+n)
Tag：
数据结构
模式
复杂度
时间：2022-01-04 13:53:01
上一篇：
StrIndex（‘DATASTRUCTURE'，1,‘STR'）=（）。
下一篇：
StrIndex(‘IndexofString’,1,‘Str’）=（）。
相关答案
1.
假设空串是任何串的子串，则串S='Computer'的子串个数是（）。
2.
模式串t=‘abcaabbcabcaabdab'，该模式串的next函数值为（）。
3.
模式串‘ababaaababaa'的next函数值为（）。
4.
设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）。
5.
两个串相等的充要条件是（）。
6.
串的长度是指（）。
7.
串是一种特殊的线性表，其特殊性体现在（）。
8.
下面关于串的叙述不正确的是（）。
9.
模式串ababc对应的next值为01123。
10.
KMP算法最终只需要讨论模式串本身就可以。
热门答案
1.
串的简单模式匹配算法的时间复杂度达到平方阶。
2.
串是一种特殊的线性表。
3.
线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。
4.
栈和队列的存储方式，既可以是顺序方式，也可以是链式方式。（）
5.
栈和队列都是线性表，只是在插入和删除时受到了一些限制。（）
6.
两顺序栈共享空间，也存在空间溢出问题。（）
7.
任何一个递归过程都可以转换成非递归过程。（）
8.
顺序栈因为是顺序存储，所以可以随机存取栈中任意元素。（）
9.
两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出，应把两个栈的栈底分别设在这片内存空间的两端。（）
10.
消除递归不一定需要使用栈，此说法（）。