- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- void get_next(char* p, int plen, int* next){
- int q=0, k=0;
- next[0] = 0;
- for(q=1; q < plen; q++){
- while(k>0 && p[q] != p[k]){
- k = next[k];
- }
- if(p[q]==p[k])
- k++;
- next[q]=k;
- }
- }
- void kmp_match(char* t, char* p){
- int plen = strlen(p);
- int *next = (int*)malloc(sizeof(int)*plen);
- int q = 0, i=0, tlen = strlen(t);
- get_next(p, plen, next);
- for(i=0; i < tlen; i++){
- while( q>0 && p[q]!=t[i] ){
- q = next[q];
- }
- if(p[q]==t[i])
- ++q;
- if(q==plen){
- printf("Match pos = %d\\n", i-plen+1);
- q = next[q];
- }
- }
- free(next);
- }
- int main(){
- int i=0;
- char* p = "abcab";
- char* t = "ababcaabababcababcabababababaxxb";
- int plen = strlen(p);
- kmp_match(t,p);
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/040520149433.html
来源: http://www.codesnippet.cn/detail/040520149433.html