#include<stdio.h>
#include<stdlib.h>
#include
using namespace std
#define N 50
#define MAXSIZE 100
#define OK 1
#define ERROR 0
; typedef int Status
; typedef char ElemType
; typedef struct {
char* ch;
int length;
}HString;
//初始化
Status StrInit(HString& T)
{
T.ch = new ElemType[MAXSIZE];
if (!T.ch)
return ERROR;
T.ch[1] = '\0';
T.length = 0;
return OK;
}
//创建串
Status CreateStr(HString& T, int len)
{
char x;
int i;
for (i = 0; i < len; i++)
{
cin >> x;
T.ch[i] = x;
}
T.ch[i] = '\0';
T.length = len;
return OK;
}
Status StrDisplay(HString& T)
{
int i;
for (i = 0; i < T.length; i++)
{
printf("%c", T.ch[i]);
}
return OK;
}
//计算next函数值
void getnext(HString T, int next[])
{
int i = 1, j = 0;
next[1] = 0;
while (i < T.length)
{
if (j == 0 || T.ch[i] == T.ch[j])
{
++i;
++j;
next[i] = j;
}
else
j = next[j];
}
}
//KMP算法
int Index_KMP_NEXT(HString S, HString T, int next[])
{
getnext(T, next);
int i = 1, j = 1, sum = 0;
while (i <= S.length && j <= T.length)
{
sum++;
if (j == 0 || S.ch[i-1] == T.ch[j-1])
{
++i;
++j;
}
else
{
j = next[j];
}
cout << "\n一共比较了" << sum << "次" << endl;
if (j > T.length)
return (i - T.length);
else
return -1;
}
}
int main()
{
HString S;
HString T;
StrInit(S);
cout << "S:" << StrInit(S) << endl;
StrInit(T);
cout << "T:" << StrInit(T) << endl;
int m;
printf("S串长为:");
cin >> m;
printf("输入串S:");
CreateStr(S, m);
StrDisplay(S);
int n;
printf("\nT串长为:");
cin >> n;
printf("输入串T:");
CreateStr(T, n);
StrDisplay(T);
int* next = new int[T.length+1];
getnext(T, next);
int y = Index_KMP_NEXT(S, T, next);
if (y == -1)
cout << " 匹配不成功" << endl;
else
cout << "匹配成功" << "匹配结果:" << y << endl;
return OK;
system("pause")
}