现有主串:a b a a b a b a a b a b a b a c a, 模式串:a b a b a c 。请写出模式串的next函数,画出用KMP方法进行匹配的过程,并统计出比较的次数。

时间: 2024-05-30 19:08:19 浏览: 84
模式串的next数组为:[-1, 0, 0, 1, 0, 0]。 匹配过程如下: 1. 在主串中匹配到第一个字符 a,模式串匹配到第一个字符 a,比较次数为1。 2. 在主串中匹配到第二个字符 b,模式串匹配到第二个字符 b,比较次数为2。 3. 在主串中匹配到第三个字符 a,模式串匹配到第三个字符 a,比较次数为3。 4. 在主串中匹配到第四个字符 a,模式串匹配到第四个字符 b,不匹配,模式串向前移动2个字符,比较次数为3。 5. 在主串中匹配到第五个字符 b,模式串匹配到第一个字符 a,不匹配,模式串向前移动1个字符,比较次数为4。 6. 在主串中匹配到第六个字符 a,模式串匹配到第二个字符 b,不匹配,模式串向前移动1个字符,比较次数为5。 7. 在主串中匹配到第七个字符 b,模式串匹配到第一个字符 a,不匹配,模式串向前移动1个字符,比较次数为6。 8. 在主串中匹配到第八个字符 a,模式串匹配到第二个字符 b,不匹配,模式串向前移动1个字符,比较次数为7。 9. 在主串中匹配到第九个字符 a,模式串匹配到第一个字符 a,不匹配,模式串向前移动1个字符,比较次数为8。 10. 在主串中匹配到第十个字符 b,模式串匹配到第二个字符 b,不匹配,模式串向前移动1个字符,比较次数为9。 11. 在主串中匹配到第十一个字符 a,模式串匹配到第一个字符 a,不匹配,模式串向前移动1个字符,比较次数为10。 12. 在主串中匹配到第十二个字符 b,模式串匹配到第二个字符 b,不匹配,模式串向前移动1个字符,比较次数为11。 13. 在主串中匹配到第十三个字符 a,模式串匹配到第一个字符 a,不匹配,模式串向前移动1个字符,比较次数为12。 14. 在主串中匹配到第十四个字符 b,模式串匹配到第二个字符 b,不匹配,模式串向前移动1个字符,比较次数为13。 15. 在主串中匹配到第十五个字符 a,模式串匹配到第一个字符 a,不匹配,模式串向前移动1个字符,比较次数为14。 16. 在主串中匹配到第十六个字符 c,模式串匹配到第二个字符 c,不匹配,模式串向前移动1个字符,比较次数为15。 17. 在主串中匹配到第十七个字符 a,模式串匹配到第一个字符 a,不匹配,模式串向前移动1个字符,比较次数为16。 因此,匹配过程一共进行了16次比较。

相关推荐

最新推荐

recommend-type

浅析基于B/S架构项目管理系统的优势

随着全球化进程的加速,企业面临着更为复杂的业务环境,传统的C/S(客户端/服务器)架构的项目管理系统已无法满足现代企业的快速响应需求。B/S(浏览器/服务器)架构的项目管理系统应运而生,它以其独特的优点,逐渐...
recommend-type

图书管理本系统是采用vb6.0作为前台开发工具,SQL Server作为后台数据库平台的基于C/S的两层模式的管理系统

本系统采用了经典的VB6.0作为前端开发工具,配合强大的SQL Server作为后台数据库平台,构建了一个基于C/S(客户端/服务器)架构的两层管理模式。 首先,VB6.0是微软公司推出的Visual Basic版本,以其直观的拖放式...
recommend-type

mysql ocp题库总结

选项C(SET GLOBAL enforce_gtid_consistency=ON)是开启GTID一致性检查,这在问题发生后并不解决现有的冲突。选项B和D的GTID_NEXT设置方式不正确,因为它们试图设置一个特定的GTID,而不是注入一个空事务来解决冲突...
recommend-type

滤波参考P32-MCP25XXFD-FRM,-CAN-FD-Controller-Module-DS20005678D.pdf

MCP2517FD是Microchip Technology Inc.推出的一款高性能、经济实惠的外部CAN(Controller Area Network)FD(Flexible Data-rate)控制器。该器件旨在为微控制器提供便捷的CAN FD功能扩展,尤其适用于那些不具备内置...
recommend-type

EPS快捷键操作方法.docx

在加线或选择集状态下,按下<A>键可以在光标位置添加一个新的点到当前点列的末尾,这对于构建几何形状或编辑现有线段非常有用。 2. **闭合/打开快捷键**:<C> 使用<C>键可以关闭或打开当前线列。如果线列是开放的...
recommend-type

C++标准程序库:权威指南

"《C++标准程式库》是一本关于C++标准程式库的经典书籍,由Nicolai M. Josuttis撰写,并由侯捷和孟岩翻译。这本书是C++程序员的自学教材和参考工具,详细介绍了C++ Standard Library的各种组件和功能。" 在C++编程中,标准程式库(C++ Standard Library)是一个至关重要的部分,它提供了一系列预先定义的类和函数,使开发者能够高效地编写代码。C++标准程式库包含了大量模板类和函数,如容器(containers)、迭代器(iterators)、算法(algorithms)和函数对象(function objects),以及I/O流(I/O streams)和异常处理等。 1. 容器(Containers): - 标准模板库中的容器包括向量(vector)、列表(list)、映射(map)、集合(set)、无序映射(unordered_map)和无序集合(unordered_set)等。这些容器提供了动态存储数据的能力,并且提供了多种操作,如插入、删除、查找和遍历元素。 2. 迭代器(Iterators): - 迭代器是访问容器内元素的一种抽象接口,类似于指针,但具有更丰富的操作。它们可以用来遍历容器的元素,进行读写操作,或者调用算法。 3. 算法(Algorithms): - C++标准程式库提供了一组强大的算法,如排序(sort)、查找(find)、复制(copy)、合并(merge)等,可以应用于各种容器,极大地提高了代码的可重用性和效率。 4. 函数对象(Function Objects): - 又称为仿函数(functors),它们是具有operator()方法的对象,可以用作函数调用。函数对象常用于算法中,例如比较操作或转换操作。 5. I/O流(I/O Streams): - 标准程式库提供了输入/输出流的类,如iostream,允许程序与标准输入/输出设备(如键盘和显示器)以及其他文件进行交互。例如,cin和cout分别用于从标准输入读取和向标准输出写入。 6. 异常处理(Exception Handling): - C++支持异常处理机制,通过throw和catch关键字,可以在遇到错误时抛出异常,然后在适当的地方捕获并处理异常,保证了程序的健壮性。 7. 其他组件: - 还包括智能指针(smart pointers)、内存管理(memory management)、数值计算(numerical computations)和本地化(localization)等功能。 《C++标准程式库》这本书详细讲解了这些内容,并提供了丰富的实例和注解,帮助读者深入理解并熟练使用C++标准程式库。无论是初学者还是经验丰富的开发者,都能从中受益匪浅,提升对C++编程的掌握程度。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

Parallelization Techniques for Matlab Autocorrelation Function: Enhancing Efficiency in Big Data Analysis

# 1. Introduction to Matlab Autocorrelation Function The autocorrelation function is a vital analytical tool in time-domain signal processing, capable of measuring the similarity of a signal with itself at varying time lags. In Matlab, the autocorrelation function can be calculated using the `xcorr
recommend-type

怎样使scanf函数和printf在同一行表示

在C语言中,`scanf` 和 `printf` 通常是分开使用的,因为它们的功能不同,一个负责从标准输入读取数据,另一个负责向标准输出显示信息。然而,如果你想要在一行代码中完成读取和打印,可以创建一个临时变量存储 `scanf` 的结果,并立即传递给 `printf`。但这种做法并不常见,因为它违反了代码的清晰性和可读性原则。 下面是一个简单的示例,展示了如何在一个表达式中使用 `scanf` 和 `printf`,但这并不是推荐的做法: ```c #include <stdio.h> int main() { int num; printf("请输入一个整数: ");
recommend-type

Java解惑:奇数判断误区与改进方法

Java是一种广泛使用的高级编程语言,以其面向对象的设计理念和平台无关性著称。在本文档中,主要关注的是Java中的基础知识和解惑,特别是关于Java编程语言的一些核心概念和陷阱。 首先,文档提到的“表达式谜题”涉及到Java中的取余运算符(%)。在Java中,取余运算符用于计算两个数相除的余数。例如,`i % 2` 表达式用于检查一个整数`i`是否为奇数。然而,这里的误导在于,Java对`%`操作符的处理方式并不像常规数学那样,对于负数的奇偶性判断存在问题。由于Java的`%`操作符返回的是与左操作数符号相同的余数,当`i`为负奇数时,`i % 2`会得到-1而非1,导致`isOdd`方法错误地返回`false`。 为解决这个问题,文档建议修改`isOdd`方法,使其正确处理负数情况,如这样: ```java public static boolean isOdd(int i) { return i % 2 != 0; // 将1替换为0,改变比较条件 } ``` 或者使用位操作符AND(&)来实现,因为`i & 1`在二进制表示中,如果`i`的最后一位是1,则结果为非零,表明`i`是奇数: ```java public static boolean isOdd(int i) { return (i & 1) != 0; // 使用位操作符更简洁 } ``` 这些例子强调了在编写Java代码时,尤其是在处理数学运算和边界条件时,理解运算符的底层行为至关重要,尤其是在性能关键场景下,选择正确的算法和操作符能避免潜在的问题。 此外,文档还提到了另一个谜题,暗示了开发者在遇到类似问题时需要进行细致的测试,确保代码在各种输入情况下都能正确工作,包括负数、零和正数。这不仅有助于发现潜在的bug,也能提高代码的健壮性和可靠性。 这个文档旨在帮助Java学习者和开发者理解Java语言的一些基本特性,特别是关于取余运算符的行为和如何处理边缘情况,以及在性能敏感的场景下优化算法选择。通过解决这些问题,读者可以更好地掌握Java编程,并避免常见误区。