这里只有模板，并不作讲解，仅为路过的各位做一个参考以及用做自己复习的资料，转载注明出处。

KMP字符串匹配

/*Copyright: Copyright (c) 2018*Created on 2018-11-06*Author: 十甫*Version 1.0 *Title: KMP*Time: inf mins*/#include
    
     #include
     
      #include
      
       using namespace std;const int size = 1000005;char a[size], b[size];int next[size];int main() {	memset(next, 0, sizeof(next));	scanf("%s%s", a + 1, b + 1);	int n = strlen(b + 1), m = strlen(a + 1);	next[1] = 0;	for(int i = 2, j = 0;i <= n;i++) {		while(j && b[i] != b[j + 1]) {			j = next[j];		}		if(b[i] == b[j + 1]) {			j++;		}		next[i] = j;	}	for(int i = 1, j = 0;i <= m;i++) {		while(j && a[i] != b[j + 1]) {			j = next[j];		}		if(a[i] == b[j + 1]) {			j++;		}		if(j == n) {			printf("%d\n", i - n + 1);			j = next[j];		}	}	for(int i = 1;i <= n;i++) {		printf("%d ", next[i]);	}	printf("\n");	return 0;}