kmp.cpp

来自「内有KMP的模板和pku2406」· C++ 代码 · 共 65 行

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

void get_next(const char *Pattern,int *next)
{
	int j=0,k=-1;
	next[0] = -1;
	for(;Pattern[j];){
		if(k!=-1&&Pattern[k]!=Pattern[j]){
			k = next[k];
		}//if
		++j;++k;
		if(Pattern[k]==Pattern[j]){
			next[j] = next[k];
		}else{
			next[j] = k;
		}//if
	}//for
}

int KMP(const char *Text, const char *Pattern, int pos)
{
	if(!Text||!Pattern||!Text[0]||!Pattern[0]){
		return -1;
	}
	int len = strlen(Pattern);
	int *next = new int(len+1);
	get_next(Pattern,next);
	
	int i = pos, j = 0;
	while(Text[i]&&Pattern[j]){
		if(Text[i]==Pattern[j]){
			++i;++j;
		}else{
			if(next[j]!=-1){
				j = next[j];
			}else{
				j = 0;++i;
			}//if
		}//if
	}//while
	delete []next;
	
	
	if(Pattern[j]=='\0'){
		return i - len;
	}else{
		return -1;
	}
}

int main(int argc, char **argv) {
	//freopen("in","r",stdin);
	//freopen("out","w",stdout);
	char s[100], t[100];
	scanf("%s",s);
	scanf("%s",t);
	int res = KMP(s,t,0);
	printf("%d\n",res);
	return 0;
}