#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])這個判斷語句裡可以寫打印語句,可以分別看到匹配雙方的值