// ■文字列照合における力任せ法，KMP法，BM法の比較
#include "stdio.h"
#include "string.h"
int brute(char str[], char pat[]){
	int p1,p2,N1,N2; p1=p2=0;N1=strlen(str); N2=strlen(pat);
	printf("\n 力任せ法におけるp1の値 : ");
	while(p1<N1 && p2<N2){
		printf(" %d",p1);
		if(str[p1]==pat[p2]){ p1++        ; p2++;}
		else                { p1 -= (p2-1); p2=0;printf("/");}
	}
	if(p2==N2) return (p1-p2);
	return -1;
}
int KMP(char str[], char pat[]){
	int p1, p2, N1=strlen(str), N2=strlen(pat);
	int skip[256]; for(p1=0;p1<N2;p1++)skip[p1]=0;
	p1=1;p2=0;    // スキップテーブル生成
	while(p1<N2){
		if(pat[p1]==pat[p2]) skip[++p1] = ++p2;
		else if(p2==0)       skip[++p1] = p2;
		else                 p2 = skip[p2];
	}
	printf("\n KMP法におけるスキップテーブル : ");
	for(int i=0; i<N2; i++) printf(" %d", skip[i]);
	p1 = p2 =0; printf("\n KMP法におけるp1の値 : ");
	while(p1<N1 && p2<N2){
		printf(" %d",p1);
		if(str[p1]==pat[p2]){p1++;p2++;}
		else if(p2==0)      p1++;
		else                {p2=skip[p2];printf("/");}
	}
	if(p2==N2) return p1 - p2; else return -1;
}
int BM(char str[], char pat[]){
	int p1,p2,N1,N2; p1=p2=0;N1=strlen(str); N2=strlen(pat);
	int skip[256];
	for(p1=0;p1<256;p1++) skip[p1]=N2;//スキップテーブル生成
	for(p1=0;p1<=N2-1;p1++)skip[pat[p1]] = N2 - p1 - 1;
	printf("\n BM法におけるスキップテーブル : ");
	for(int i=0; i<256; i++) {//スキップテーブル表示
		if(i %32==0)printf("\n");printf(" %d", skip[i]);
	}
	p1 = N2-1; printf("\n BM法におけるp1の値 : ");
	while(p1<N1){
		printf(" %d",p1);
		for(p2=N2-1;str[p1]==pat[p2];p1--, p2--){
			if(p2!=(N2-1))printf(" %d",p1);
			if(p2==0) return p1;
		}
		p1+=skip[str[p1]]; printf("/");
	}
	return -1;
}
int main(){
	char str[]="PSEASEASER", pat[]="SEASER";
	printf("\n テキスト [%s]\n 照合パターン  [%s]\n (/は探索やりなおし箇所)\n",str, pat );
	printf("\n %d\n", brute(str,pat));
	printf("\n %d\n", KMP(str,pat));
	printf("\n %d\n", BM(str,pat));
	getchar();
}