[单选题]
关于复杂度和效率的解释：
假设主串长度m，子串长度n；
KMP算法的复杂度为O(m+n)，其中的n是因为要计算next数组而产生的，此后进行查找匹配时，效率是m（看主串游标的移动，子串游标除了跳转外和主串游标一起移动），跳转时的比较忽略不计，合起来是m+n；
而暴力算法我们一般认为它的复杂度为O(m*n)，其实这只是一种简略表示，精确是n*(m-n+1)，
根据复杂度的表达式我们可以知道，它们效率的差别只取决于两个串的长度，当m==n时，KMP：O(2m)，暴力：O(m)，此时暴力快一点
关于next数组的简要说明：
原理是：当主串和子串在当前位置只有部分匹配时，主串中匹配部分存在后缀C和子串匹配部分的后缀B相等，所以主串当前后缀C == 子串前缀A，那么子串游标就直接从B往前跳到A就可以继续和主串比较了。
作用是：用于子串游标跳转（精确定位，这正是KMP节省时间的地方，暴力算法不知道要跳到哪里就只能苟且了）；
方法是：求子串前缀A、区间后缀B的匹配；
子串next数组的具体求解过程建议专门找博客看看。
编辑于 2019-09-23 23:15:28
回复(0)
部分匹配表：
"前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合；
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，
－ "A"的前缀和后缀都为空集，共有元素的长度为0；
－ "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
－ "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
－ "ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
－ "ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
－ "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
－ "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
kmp算法：１后移， 直到字符串有一个字符，与搜索词的第一个字符相同为止．２接着比较字符串和搜索词的下一个字符，直到字符串有一个字符，与搜索词对应的字符不相同为止３根据部分匹配表，移动位数 = 已匹配的字符数 - 对应的部分匹配值４ 逐位比较，直到搜索词的最后一位
发表于 2017-05-17 13:05:53
回复(3)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
