使用c++实现应用Horspool算法在一个长度为n(n<=1000)的文本中,查找一个长度为m(n>=m)的模式。如果模式位于文本串中,返回模式首次出现的位置;如果模式不在文本串中,返回-1。文本字符集为ASCII码。 【输入形式】第一行为文本串;第二行为模式串 【输出形式】第一行为文本串;第二行为模式串;第三行开始依次为模式串中第1个到第m-1个字符c及其对应的移动距离T(c)值;倒数第二行为字符集中其他字符的移动距离;最后一行为模式首次出现的位置。

时间: 2024-02-28 22:56:53 浏览: 22
好的,我会尽力回答你的问题。以下是C++代码实现Horspool算法查找模式串的过程。假设文本串为text,模式串为pattern,文本串长度为n,模式串长度为m。 ```c++ #include <iostream> #include <cstring> using namespace std; const int MAXN = 1005; const int MAXM = 105; const int MAXCHAR = 256; // ASCII码字符集大小 int n, m; char text[MAXN], pattern[MAXM]; int jump[MAXCHAR]; // 记录字符移动距离 void init_jump() { memset(jump, m, sizeof(jump)); // 初始化所有字符移动距离为m for (int i = 0; i < m - 1; i++) { jump[pattern[i]] = m - 1 - i; } } int horspool() { int i = m - 1, j; while (i < n) { j = m - 1; while (text[i] == pattern[j]) { if (j == 0) return i; i--; j--; } i += jump[text[i]]; } return -1; } int main() { cin.getline(text, MAXN); cin.getline(pattern, MAXM); n = strlen(text); m = strlen(pattern); init_jump(); for (int i = 0; i < m - 1; i++) { cout << pattern[i] << " " << jump[pattern[i]] << endl; } for (int i = 0; i < MAXCHAR; i++) { if (jump[i] != m) { cout << (char)i << " " << jump[i] << endl; } } int pos = horspool(); cout << pos << endl; return 0; } ``` 代码实现中,init_jump函数用于初始化字符移动距离,jump数组记录了每个字符在模式串中出现的位置距离末尾的距离。horspool函数用于查找模式串,其中i指向文本串中当前匹配的位置,j指向模式串中当前匹配的位置。如果匹配成功,返回模式串首次出现的位置,否则返回-1。 在输出中,第三行到倒数第二行分别输出了模式串中每个字符的移动距离和字符集中其他字符的移动距离。最后一行输出了模式串首次出现的位置。

相关推荐

最新推荐

recommend-type

pre_o_1csdn63m9a1bs0e1rr51niuu33e.a

pre_o_1csdn63m9a1bs0e1rr51niuu33e.a
recommend-type

matlab建立计算力学课程的笔记和文件.zip

matlab建立计算力学课程的笔记和文件.zip
recommend-type

FT-Prog-v3.12.38.643-FTD USB 工作模式设定及eprom读写

FT_Prog_v3.12.38.643--FTD USB 工作模式设定及eprom读写
recommend-type

matlab基于RRT和人工势场法混合算法的路径规划.zip

matlab基于RRT和人工势场法混合算法的路径规划.zip
recommend-type

matlab基于matlab的两步定位软件定义接收机的开源GNSS直接位置估计插件模块.zip

matlab基于matlab的两步定位软件定义接收机的开源GNSS直接位置估计插件模块.zip
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

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

实现实时数据湖架构:Kafka与Hive集成

![实现实时数据湖架构:Kafka与Hive集成](https://img-blog.csdnimg.cn/img_convert/10eb2e6972b3b6086286fc64c0b3ee41.jpeg) # 1. 实时数据湖架构概述** 实时数据湖是一种现代数据管理架构,它允许企业以低延迟的方式收集、存储和处理大量数据。与传统数据仓库不同,实时数据湖不依赖于预先定义的模式,而是采用灵活的架构,可以处理各种数据类型和格式。这种架构为企业提供了以下优势: - **实时洞察:**实时数据湖允许企业访问最新的数据,从而做出更明智的决策。 - **数据民主化:**实时数据湖使各种利益相关者都可
recommend-type

2. 通过python绘制y=e-xsin(2πx)图像

可以使用matplotlib库来绘制这个函数的图像。以下是一段示例代码: ```python import numpy as np import matplotlib.pyplot as plt def func(x): return np.exp(-x) * np.sin(2 * np.pi * x) x = np.linspace(0, 5, 500) y = func(x) plt.plot(x, y) plt.xlabel('x') plt.ylabel('y') plt.title('y = e^{-x} sin(2πx)') plt.show() ``` 运行这段
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。