kmp模板

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int next[1002],sublen,poslen;
char sub[1002],pos[10002];

void get_next(){
	int i,j;
	next[0] = -1;
	i = 0;
	j = -1;
	while(i < sublen){
		if(j == -1 || sub[i] == sub[j]){
			i ++;
			j ++;
			next[i] = j;
		}
		else
		    j = next[j];
	} 
}

int main(){
	int i,j;
	while(scanf("%s%s",pos,sub) != EOF){
		get_next();
		sublen = strlen(sub);
		poslen = strlen(pos);
		i = 0;
		j = 0;
		while(i<poslen && j<sublen){
			if(j == -1 || pos[i] == sub[j]){
				i ++;
				j ++;
			}else{
				j = next[j];
			}
		}
		if(j >= sublen)
		    printf("%d
",i-j);
	}
	return 0;
}