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;
}