实验4-串模式匹配(BF和KMP算法)
实验目的
- 掌握串的定义及基本操作的实现;
- 掌握串的模式匹配算法及实现。
代码
#include <iostream>
#include <cstring>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAX_STR_LEN 255 // 用户可在 255(1 个字节)以内定义最大串长
typedef int Status;
typedef char SString[MAX_STR_LEN + 1]; // 0 号单元存放串的长度
Status StrAssign(SString T, const char *chars)
{ //生成一个其值等于chars的串T
int i;
if (strlen(chars) > MAX_STR_LEN)
return ERROR;
T[0] = strlen(chars); //第1个单元存放串的长度
for (i = 1; i <= T[0]; i++)
T[i] = chars[i - 1];
return OK;
}
void StrPrint(SString T)
{
int i;
for (i = 1; i <= T[0]; i++)
cout << T[i];
printf("\n");
}
int StrLength(SString S)
{
return S[0];
}
//用T返回S1和S2联接而成的新串,若未截断,则返回TRUE,否则返回FALSE
bool Concat(SString T, SString S1, SString S2)
{
int i;
if (S1[0] + S2[0] <= MAX_STR_LEN)
{ // 未截断
for (i = 1; i <= S1[0]; i++)
T[i] = S1[i];
for (i = 1; i <= S2[0]; i++)
T[S1[0] + i] = S2[i];
T[0] = S1[0] + S2[0]; // 连接之后的长度
return true;
}
else
{ // 截断 S2
for (i = 1; i <= S1[0]; i++)
T[i] = S1[i];
for (i = 1; i <= MAX_STR_LEN - S1[0]; i++)
T[S1[0] + i] = S2[i];
T[0] = MAX_STR_LEN;
return false;
}
}
//算法4.1 BF算法
int Index_BF(SString S, SString T, int pos)
{
//返回模式T在主串S中第pos个字符之后第s一次出现的位置。若不存在,则返回值为0
//其中,T非空,1≤pos≤StrLength(S)
int i = pos;
int j = 1;
if (pos <= 0 || pos > StrLength(S)) // 确保 pos 有效
return 0;
while (i <= S[0] && j <= T[0])
{
if (S[i] == T[j])
{
i++;
j++;
} //继续比较后继字符
else
{
i = i - j + 2;
j = 1;
} //指针后退重新开始匹配
}
if (j > T[0])
return i - j + 1;
else
return 0;
return 0;
} //Index
//算法4.3 计算next函数值
void get_next(SString T, int next[])
{ //求模式串T的next函数值并存入数组next
int i = 1, j = 0;
next[1] = 0; // next[0] 不存放数据
while (i < T[0])
if (j == 0 || T[i] == T[j])
{
i++;
j++;
next[i] = j;
}
else
j = next[j];
} //get_next
//算法4.2 KMP算法
int Index_KMP(SString S, SString T, int pos, int next[])
{ // 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
//其中,T非空,1≤pos≤StrLength(S)
if (pos <= 0 || pos > StrLength(S))
return 0;
int i = pos, j = 1;
while (i <= S[0] && j <= T[0])
if (j == 0 || S[i] == T[j]) // 继续比较后继字
{
i++;
j++;
}
else
j = next[j]; // 模式串向右移动
if (j > T[0]) // 匹配成功
return i - j + 1;
else
return 0;
} //Index_KMP
//算法4.4 计算next函数修正值
void get_nextval(SString T, int nextval[])
{ // 求模式串T的next函数修正值并存入数组nextval
int i = 1, j = 0;
nextval[1] = 0;
while (i < T[0])
if (j == 0 || T[i] == T[j])
{
i++;
j++;
if (T[i] != T[j])
nextval[i] = j;
else
nextval[i] = nextval[j];
}
else
j = nextval[j];
} //get_nextval
int main()
{
int i, *next;
char ch1[80], ch2[80];
SString S1, S2, S, SUB; // 定义串,第一个单元存储串的长度
cout << "请输入第一个字符串:";
cin >> ch1;
StrAssign(S1, ch1);
StrPrint(S1);
cout << "请输入第二个字符串:";
cin >> ch2;
StrAssign(S2, ch2);
StrPrint(S2);
cout << "------------------------------------------------\n";
cout << "第一个字符串长度为: " << StrLength(S1) << endl;
cout << "第二个字符串长度为: " << StrLength(S2) << endl;
cout << "\n============连接两个字符串构造主串==============\n";
Concat(S, S1, S2); //用 S 返回 S1 和 S2 联接而成的新串
cout << "主串长度为: " << StrLength(S) << endl;
cout << "主串为: ";
StrPrint(S);
cout << "请输入子串:";
cin >> ch2;
StrAssign(SUB, ch2);
cout << "子串长度为: " << StrLength(SUB) << endl;
cout << "\n---------------BF 匹配算法及实现----------------\n";
i = Index_BF(S, SUB, 1); // 利用算法 4.6 求得串 SUB 在 S 中首次匹配的位置 i
if (i)
printf("主串和子串在第%d 个字符处首次匹配\n", i);
else
printf("主串和子串匹配不成功\n");
cout << "\n---------------KMP 匹配算法及实现---------------\n";
next = new int[StrLength(SUB) + 1];
get_next(SUB, next); // 利用算法 4.7,求得 next 数组,存于 next 中
printf("子串的 next 数组为: ");
for (i = 1; i <= StrLength(SUB); i++)
cout << *(next + i);
printf("\n");
i = Index_KMP(S, SUB, 1, next); // 利用算法 4.6 求得串 SUB 在 S 中首次匹配的位置
if (i)
printf("主串和子串在第%d 个字符处首次匹配\n", i);
else
printf("主串和子串匹配不成功\n");
cout << "\n--------------KMP改进匹配算法及实现-------------\n";
get_nextval(SUB, next); // 利用算法 4.8,求得 next 数组,存于 next 中
printf("子串的 nextval 数组为: ");
for (i = 1; i <= StrLength(SUB); i++)
cout << *(next + i);
printf("\n");
i = Index_KMP(S, SUB, 1, next); // 利用算法 4.6 求得串 SUB 在 S 中首次匹配的位置 i
if (i)
printf("主串和子串在第%d 个字符处首次匹配\n", i);
else
printf("主串和子串匹配不成功\n");
getchar();
return 0;
}
运行截图
OOP版
还没写。。。