数据结构——KMP模式匹配算法

/*-----------------KMP匹配-----------------*/
/**
 * Function 获取要查找的目标字符串的next数组
 * @param:
 *    str: 指向目标字符串的指针
 *    next: 指向next数组的指针
 * @return 指向next数组的指针
 */
void getNext(char *str,int *next)
{
	int i = 0;
	int j = -1;
    int len = strlen(str);
	next[0] = -1;
	while(i < (len-1) )
	{
		if(j == -1 || str[i] == str[j])
		{
			i++;
			j++;
            if(str[i] != str[j])
			    next[i] = j;
            else
                next[i] = next[j];
		}
		else
        {
			j = next[j];
		}	
	}
}


/**
 * Function KMP算法匹配查找子串
 * @param:
 *    str_o: 原始串  original string
 *    str_t: 要查找的目标字符串  target string
 *    next: 
 * @return 指向next数组的指针
 */
char *kmp(char *str_o, char *str_t, int *next)
{
	int cnt_str_o = 0, cnt_str_t = 0; // 记录原始串与目标串 进行对比的下标
	int len_str_o = strlen(str_o);
	int len_str_t = strlen(str_t);
	while(cnt_str_o < len_str_o && cnt_str_t < len_str_t)
	{
		if (cnt_str_t == -1 || str_o[cnt_str_o] == str_t[cnt_str_t])
		{
			cnt_str_o++;
			cnt_str_t++;
		}
		else
		{
			cnt_str_t = next[cnt_str_t];
	    }
	}
	if(cnt_str_t >= len_str_t)
		return str_o + (cnt_str_o - cnt_str_t);
	return NULL;
}

/**
 * kmp.c
 * 
 * Created on: 2020年1月31日
 *     Author: Beyonderwei
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


// 测试部分
int main(void)
{
    char *str1 = "123456789 abab 123456789"; // 注意空格也算一个字符
    char *str2 = "abab";
    char *status = NULL;
    int next[strlen(str2)];
    getNext(str2, next);

    // 测试普通查找方法
    status = strStr(str1, str2);
    if (status != NULL)
    {
        printf("在原始字符串中子串位置第一个字符:%c\n", *status);
        printf("子串在原始字符串中的位置：%d\n", (status-str1));
    }

    // 测试kmp算法查找
    status = kmp(str1, str2, next);
    if (status != NULL)
    {
        printf("在原始字符串中子串位置第一个字符:%c\n", *status);
        printf("子串位置：%d\n", (status-str1));
    }

    
    printf("Hello World!");
    return 1;
}