掌握简单匹配算法及模式匹配KMP算法的思想
#include <iostream>#include <stdlib.h>
#include <string>
#include <conio.h>
#include<stdio.h>
#define MAX 200
using namespace std;
char S[MAX],T[MAX];
int s = 0,t = 0;
void GetNext(char *T,int *next)//求模式串T的next函数值并存入数组next
{
int j,k;
j = 0,k = -1,next[0] = -1;
while(j<t-1)
{
if(k == -1||T[j] == T[k])
{
j ++;
k ++;
if(T[j]!=T[k])
next[j] = k;
else
next[j] = next[k];
}
else
{
k = next[k];
}
}
}
int Index_KMP(char *S,char *T,int &x)
//利用模式串T的next函数求T在主串S中第x个字符之后的位置的KMP算法。其中T非空，1<x<strlen(S)。
{
int next[200];
int i,j;
i = 0;j = 0;
GetNext(T,next);
while(i<s&&j<t)
{
if(j == -1||S[i] == T[j])//继续比较后继字符
{
i ++;
j ++;
}
else//模式串向右移动
{
j = next[j];
}
}
if(j>=t)//匹配成功
x = i-t+1;
else
x = -1;
return 1;
}
int main()//主函数
{
int x;
printf("Please Input The String Of S:\n");
gets(S);
printf("\n");
printf("Please Input The String Of T:\n");
gets(T);
printf("\n");
s = strlen(S);
t = strlen(T);
Index_KMP(S,T,x);
printf("The String Start at %d\n",x);
system("pause");
return 0;
}
这个程序结果运行如下
：
主串：
Through a retrospective look at the mathematics teaching at USTC, this article summarizes university’s teaching achievements in past 45 years.
匹配子串：teaching
输出结果：
位置是：46
第二次出现teaching的位置怎么找阿。。这个程序就找出第一次出现的位置
此题题目如下：
设计要求：
理解模式匹配的含义，掌握简单匹配算法及模式匹配KMP算法的思想，实现以下任务：
（1）编程动态实现简单模式匹配算法及模式匹配KMP算法；
（2）根据给定的主串与模式串，给出根据两种匹配算法进行匹配的各趟匹配结果；
（3）测试用例：
主串：
Through a retrospective look at the mathematics teaching at USTC, this article summarizes university’s teaching achievements in past 45 years.
匹配子串：teaching
输出结果：
匹配子串 teaching 出现在主串中的次数为 2
2 次的匹配的位置分别是：46 102;
(4)一个应用实例如下：
要求编写建立一个文本文件，每个单词不包括空格且不跨行，单词由字符序列构成，且区分大小写；
统计给定单词在文本中出现的总次数；
检索出某个单词在文本中的行号、在该行中出现的次数及位置。
求解～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～
