#include <stdio.h> #include <stdlib.h> #include <string.h> int kmp(const char *str, const char *str_sub){ int sub_len = strlen(str_sub); if(sub_len == 0){ return 0; } int* next = (int*) calloc(sizeof(int), sub_len); int i = 0; int j = -1; next[0] = -1; while(i < sub_len){ if(j == -1 || str_sub[i] == str_sub[j]){ ++i; ++j; next[i] = j; } else { j = next[j]; } } int len = strlen(str); for(i = -1, j = -1; i < len && j < sub_len; ){ if(j == -1 || str[i] == str_sub[j]){ ++i; ++j; } else { j = next[j]; } } free(next); if(j >= sub_len){ return i - sub_len; } else { return -1; } } int main(){ char *str = "hello"; char *str_sub = "llo"; printf("str:%s, sub:%s, %d ",str, str_sub, kmp(str, str_sub)); str = "ababababb"; str_sub = "abababb"; printf("str:%s, sub:%s, %d ",str, str_sub, kmp(str, str_sub)); str = "hello"; str_sub = ""; printf("str:%s, sub:%s, %d ",str, str_sub, kmp(str, str_sub)); str = "hello"; str_sub = "hellol"; printf("str:%s, sub:%s, %d ",str, str_sub, kmp(str, str_sub)); return 0; }