KMP Implement in C

main.c

#执行的方法
#./a.out 中国国家人民政府 人民
#输出
#
#[CONSOLE:] 中国国家人民政府
#                 △
#                 ↑表示此处匹配
#
#

#include "str_match.h"

int main(int argc, char* argv[])
{
    int i;

	char *test = argv[1];
	char *sub = argv[2];

	i = kmp_match(test,sub);

	if(i != -1) {
		printf("%d\n",i);
		print_str_match(test, i - strlen(sub));
	}
	else {
		printf("\nNOT　Found！\n");
	}

	return 0;
}

str_kmp.c

#静态编译的方法 cc -o file.o -c file.c
#生成静态库文件 ar cqs libfile.a file.o
#生成二进制文件 cc -static xxx.c -L. -lfile
###################################################
#生成动态库文件 cc -shared -fPIC -o file.so file.c
#生成二进制文件 cc ./file.so xxx.c
###################################################

#include "str_match.h"

#define PPREFIX "[CONSOLE:] "

void print_str_match(const char* s, const int index)
{
    int num = strlen(PPREFIX) + index;

	printf("%s%s\n", PPREFIX, s);
	while(num--) {
		printf(" ");
	}
	printf("%s\n", "△");

}

int kmp_init(const char * str, int index[])
{

	int s_len = strlen(str);
	int i;

	index[0] = -1;

	for(i = 1; i < s_len; ++i) {
		int last = i - 1;

		while(index[last] != -1) {
			if(str[index[last] + 1] == str[i]) {
				index[i] = index[last] + 1;
				break;
			}
			else
				last = index[last];
		}

		if(index[last] == -1) {
			if(str[0] == str[i])
				index[i] = 0;
			else
				index[i] = -1;
		}
	}

	return i;
}

int kmp_match(const char* src, const char* sub)
{

	int sub_len = strlen(sub);
	int* sub_index = (int *) malloc(sub_len);
	int i,j;

	kmp_init(sub, sub_index);

	for (i = 0, j = 0; i < strlen(src) && j < sub_len; ++i) {

		while(sub[j] != src[i]) {
			if(j == 0)
				break;
			else
				j = sub_index[j] + 1;
		}

		if(sub[j] == src[i])
			++j;
	}

	if(j == sub_len)
		return i;
	else
		return -1;

}

str_match.h

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

void print_str_match(const char* s, const int index);

int kmp_init(const char *str, int index[]);
int kmp_match(const char* src, const char* sub);

算法戳这里http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm#External_links