KMP与BF,实现了一个非主流next函数
#include <stdlib.h>#include <string.h>int bf(char* text, char* patten){int i = 0;int j = 0;while(i<strlen(text) && j<strlen(patten)){if(text[i] == patten[j]){i++;j++;}else{//i回溯到 开始匹配的下一个位置 i = i-j+1;//j回溯到最开始0处 j = 0;}}//匹配到时候是j<strlen(patten)条件不满足的时候 return j>strlen(patten)-1 ? i-j : -1;}//在J位置发生不匹配以后，找到一个k使 P[0~K]==P[K+1~J]调整将J调整为K //这个方法也可以将next(j-1)求解出的子问题存储起来，这么写主要是为了好想 int next(char* patten, int j){if(j==0||j==-1){return 0;}if(patten[j]==patten[next(patten, j-1)+1]){return next(patten, j-1)+1;}else{while(1){int k = next(patten, j-1);if(patten[j]==patten[k+1]){return next(patten, k);}}}}int kmp(char* text, char* patten){int i = 0;int j = 0;while(i<strlen(text) && j<strlen(patten)){if(text[i] == patten[j] || j==0){i++;j++;}else{//j位置发生不匹配 //j通过分析模式串,计算出模式串下一个比较位置和文本不匹配位置匹配 j = next(patten, j-1);}}return j>strlen(patten)-1 ? i-j : -1;}int main(){char* text = "adjfskjfskdjsfkglsi";char* patten = "skdj";printf("%d\n",bf(text, patten));printf("%d\n",kmp(text, patten));return 0;}