KMP查找

/*!数据结构与算法（C语言版）
 * 模式匹配算法（KMP） P80-83 
 */


#include
#include


void get_next(char *s, int *p)
{//求模式串的next值并存入数组p 

int i, j, str_len;

str_len = strlen(s);
i = 1;
j = 0;
p[0] = 0;
while(i < str_len)
{
if(j == 0 || s[i] == s[j])
{
i++;
j++;
p[i - 1] = j;
}
else
{
j = p[j-1];
}
}
}


int index_KMP(char *str1, char *str2, int *p)
{//模式串str1， 主串str2，使用KMP算法在主串str2中查找str1 
int i, j;

i = 0;
j = 0;

while(i < strlen(str2) && j < strlen(str1))
{
if(str2[i] == str1[j])
{
j++;
i++;
}
else
{
if(j == 0)
i++;
else
j = p[j - 1];
}
}

if(j >= strlen(str1))
return (i - strlen(str1)); //匹配成功 
else
return -1;//匹配失败 
}


int main(void)
{
// char s1[] = "000001"; //模式串 
// char s2[] = "00000000000000000000000000000000000000000000000001"; //主串 
// char s1[] = "abcac";  //模式串 
// char s2[] = "ababcabcacbab"; //主串 
// char s1[] = "abaabc";
// char s2[] = "acabaabaabcacaabc";

char s1[] = "da";
char s2[] = "abcdefggggugugu";


int result;
int next[strlen(s1)];

get_next(s1, next);
result = index_KMP(s1, s2, next);

printf("result = %d\r\n", result);

return 0;
}