#include "stdafx.h"
#include "stdio.h"
#define MaxSize 21
typedef struct //定义结构体类型
{
char data[MaxSize];
int length;
}SqString;
void StrAssign(SqString &s, char cstr[]) //将一个字符串常量赋给串s
{
int i;
for (i = 0; cstr[i] != '\0'; i++)
s.data[i] = cstr[i];
s.length = i;
}
void GetNextval(SqString t, int nextval[]) //对模式串t求nextval[]值
{
int j = 0, k = -1;
nextval[0] = -1;
while (j {
if (k == -1 || t.data[j] == t.data[k])
{
j++; k++;
if (t.data[j] != t.data[k])
nextval[j] = k;
else
nextval[j] = nextval[k];
}
else
k = nextval[k];
}
}
int KMPIndex(SqString s, SqString t)
{
int nextval[MaxSize], i = 0, j = 0;
GetNextval(t, nextval);
while (i {
if (j == -1 || s.data[i] == t.data[j])
{
i++;
j++;
}
else j = nextval[j];
}
if (j >= t.length)
return(i - t.length);
else
return -1;
}
int main(int argc, char* argv[])
{
SqString s1, s2;
int k;
char t[21] = { 'a', 'b', 'c', 'a', 'a', 'b', 'b', 'a', 'b', 'c', 'a', 'b', 'a', 'a', 'c', 'b', 'a', 'c', 'b', 'a' };
char p[8] = { 'a', 'b', 'c', 'a', 'b', 'a', 'a' };
StrAssign(s1, t);
StrAssign(s2, p);
k = KMPIndex(s1, s2);
if (k != -1)
printf("匹配,从第%d个数开始", k);
else
printf("不匹配");
return 0;
int KMPIndex(SqString s, SqString t);函数应该是你说的匹配函数吧,
if (j == -1 || s.data[i] == t.data[j])这个判断语句里可以写打印语句,可以分别看到匹配双方的值
https://zhidao.baidu.com/question/628075345562548804.html
提供参考:http://blog.csdn.net/u014033518/article/details/38371343