北京邮电大学软件学院 2024-2024学年第1学期实验报告
课程名称： 算法与数据结构课程设计
实验名称： 字符串的模式匹配
实验完成人：
日 期： 2024 年 10月 25 日
一、 实验目的
本次实验的目的是熟悉串类型的实现方法和文本模式匹配方法，熟悉串的键盘输入获取方式。
二、 实验内容 1、 数值转换问题
2、 3、 4、
[问题描述]
设有两个字符串s和t，首先将s1与t1进行比较，直到s的某一个字符si和ti相同，
再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当s的某一个字符si与t的字符tj不同时，则s返回到本趟开始字符的下一个字符，即si-j+2，t返回到t1，继续开始下一趟的比较，重复上述过程。若t中的字符全部
5、 6、 7、
比较完，则说明本趟匹配成功，本趟的起始位置是i-j+1，否则，匹配失败。 [基本要求]
本实验要求学生掌握串的特点及顺序定长存储的方式，掌握模式匹配的基本思想及其算
法。由用户通过键盘输入建立一个主字符串和搜索串，如果主串中包含要搜索的子串，返回子串在主串中的起始位置，否则返回搜索失败。
三、 实验环境
Windows下利用vs 2024完成,语言c++
四、 实验过程描述
首先构造Astring类，内含字符数组string[],next[]，以及一些操作。
class AString
{
private:
char string[MAXLENGTH+1]; //字符数组 int length;
int next[MAXLENGTH + 1]; //KMP用 public:
AString();
static int Index(AString, AString); //暴力算法 static int Index_KMP(AString, AString); //KMP
void Get_next(); //KMP用 };
实现相应功能:
输入字符并判断，读到空格时停下。 写在构造函数中：
AString::AString() {
char temp=0; int i = 1; while (1) {
scanf(\, &temp);
if (temp == ' ' || temp == '\\n') break;
string[i] = temp; i++; }
length = i-1;
//读到回车或空格停下
string[0] = length; }
//第0位来存放长度
用暴力算法获得index：
int AString::Index(AString s,AString t) {
int i = 1, j = 1, index;
while (i <= s.length && j <= t.length) {
if (s.string[i] == t.string[j]) {
++i; ++j; } else {
i = i - j + 2; j = 1;
//分别比较，相同则同时后移
//不同则回溯
}
} }
if (j > t.length)
return i - t.length; else
return 0;
得到next[]:
void AString::Get_next() {
int j = 1, k = 0; this->next[1] = 0;
while (j <= this->length) {
if (k == 0 || this->string[j] == this->string[k]) {
++j; ++k;
this->next[j] = k; } else
k = this->next[k]; }
KMP算法：
int AString::Index_KMP(AString s, AString t) {
t.Get_next(); int i = 1,j = 1;
while (i <= s.length && j <= t.length) {
if (j == 0 || s.string[i] == t.string[j]) {
++i; ++j; }
else j =t.next[j]; }
if (j > t.length)
return i - t.length; else
return 0; }
五、 实验结果
查找成功，返回位置：
查找失败，返回0：
算法与数据结构实验报告——字符串
