洛谷P3375KMP字符串匹配

传送门

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define re register
using namespace std;
const int maxn = 1000005;

inline long long read() {
	char ch = getchar();
	long long f = 1 , x = 0;
	while(ch > '9' || ch < '0') {if(ch == '-') f = -1 ;ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 1) + ( x << 3) + ch - '0';ch = getchar();}
	return x * f;
}

char s1[maxn],s2[maxn];
int len1,len2;
int nxt[maxn];
//用于记录当匹配到模式串的第 i 位之后失配,该跳转到模式串的哪个位置

int main(){
	cin >> s1 + 1 >> s2 + 1 ;
	len1 = strlen(s1 + 1) , len2 = strlen(s2 + 1);
	nxt[0] = nxt[1] = 0; 
	int j ;//j可以看做表示当前已经匹配完的模式串的最后一位的位置 
	for(re int i = 2 ; i <= len2 ; ++i) {
		while(j && s2[i] != s2[j + 1])  j = nxt[j];
		//如果失配 ，那么就不断向回跳，直到可以继续匹配 
		if(s2[j + 1] == s2[i])  j++;
		//如果匹配成功，那么对应的模式串位置++ 
		nxt[i] = j ;
	}
	j = 0;
	for(re int i = 1 ; i <= len1 ; ++i) {
		while(j && s2[j + 1] != s1[i]) j = nxt[j];
		//此处判断j是否为0的原因在于，如果回跳到第一个字符就不 用再回跳
		if(s2[j + 1] == s1[i])  j++ ;
		if(j == len2) {
			printf("%d
",i - len2 + 1) ;
			j = nxt[j];
		}
	}
	for(re int i = 1 ; i <= len2 ; ++i)
		printf("%d " , nxt[i]);
	return 0;
}