//从串str中的pos位置起，求出与substr串匹配的子串的位置，如果str为空串，或者串中不含与substr匹配的子串，则返回-1做标记
include <stdio.h>
include <stdlib.h>
include <string.h>
define MAXSIZE 100
typedef struct Str
{
char ch[MAXSIZE];
int length;
struct Str next;
} Str;
void get_next();
int KMP(Str str, Str substr, int pos)
{
int next[MAXSIZE];
get_next(substr, next);
int i = pos, j = 1;
while (i <= str.length && j <= substr.length)
{
if (j == 0 || str.ch[i - 1] == substr.ch[j - 1])
{
i++;
j++;
}
else
{
j = next[j];
}
}
if (j > substr.length)
{
return i - substr.length - pos;
}
else
{
return -1;
}
}
void get_next(Str substr, int next[])
{
int i = 1, j = 0;
next[1] = 0;
while (i < substr.length)
{
if (j == 0 || substr.ch[i - 1] == substr.ch[j - 1])
{
i++;
j++;
next[i] = j;
}
else
{
j = next[j];
}
}
}
int main()
{
int position, pos;
int next[MAXSIZE];
printf("输入pos:");
scanf("%d", &pos);
Str s1[] = {"acabaabaabcacaabc", 17};
Str s2[] = {"abaabcac", 8};
printf("主串：%s\n", s1->ch);
printf("模式串：%s\n", s2->ch);
printf("next数组为：");
get_next(s2, next);
for (int i = 1; i <= s2->length; i++)
{
printf("%d ", next[i]);
}
printf("\n");
position = KMP(*s1, *s2, pos);
if (position != 0)
printf("从主串第%d位起，从第%d位开始与子串匹配成功！\n", pos, position);
else
printf("can not found!");
return 0;
}
