#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 20

typedef struct String{
	char ch[MAXSIZE];
	int length;
}String;

void InitData(String str){
	str.ch[MAXSIZE];
}
//KMP 未優化 
int Index(String str,String s){
	int i=0,j=0;
	while(i<str.length && j<s.length){
		if(str.ch[i] == s.ch[j]){
			++i,++j; //相等則前進 
		}else{
			i=i-j+1;//i跟上次的多1 
			j=0;//j回到原點 
		}
		if(j==s.length) return i - s.length;
	}
	return 0;
}
//-------------start----------
//獲取未優化的next 
void get_next(String s,int next[]){
	int i=0,j=-1;
	next[0]=-1;
	while(i < s.length-1) {
		if(j == -1 || s.ch[i] == s.ch[j]){
			++i,++j;
			next[i]=j;
		}
		else j=next[j];
	}
}

//KMP 優化1
int Index_KMP(String str,String s,int next[]){
	int i=0,j=0;
	while(i<str.length && j<s.length){
		if(j == -1 || str.ch[i] == s.ch[j]){
			++i,++j; 
		}else j=next[j];
		if(j==s.length) return i - s.length;
	} 
	return 0;
} 
//-------------end----------


//-------------start---------
//獲取優化的next --> nextval
void get_nextval(String s,int nextval[]){
	int i=0,j=-1;
	nextval[0]=-1;
	while(i < s.length-1) {
		if(j == -1 || s.ch[i] == s.ch[j]){
			++i,++j;
			if(s.ch[i]!=s.ch[j]) nextval[i]=j;
			else nextval[i]=nextval[j];
		}
		else j=nextval[j];
	}
}

//KMP 優化2
int Index_KMP2(String str,String s,int nextval[]){
	int i=0,j=0;
	while(i<str.length && j<s.length){
		if(j == -1 || str.ch[i] == s.ch[j]){
			++i,++j; 
		}else j=nextval[j];
		if(j==s.length) return i - s.length;
	} 
	return 0;
} 
//-------------end---------
int main()
{
	String str;
	InitData(str);
	strcpy(str.ch,"googlcgoogleloogob");
	str.length = strlen(str.ch);
	
	String s;
	InitData(s);
	strcpy(s.ch,"google");
	s.length = strlen(s.ch);
	
	int idx=Index(str,s);
	printf("【未優化的結果,開始的下標為：】%d\n",idx);
	
	//優化1 
	int next[s.length]={0};
	get_next(s,next);
//	for(int i=0;i<s.length;i++){
//	 	printf("%d\n",next[i]);
//	}
	int idx2=Index_KMP(str,s,next);
	printf("【next未優化的結果,開始的下標為：】%d\n",idx2);

	//優化2 
	int nextval[s.length]={0};
	get_nextval(s,nextval);
//	for(int i=0;i<s.length;i++){
//	 	printf("%d\n",nextval[i]);
//	}
	int idx3=Index_KMP2(str,s,nextval);
	printf("【next優化的結果,開始的下標為：】%d\n",idx3);
	
	return 0;
 }