rt, link

测试点二下载数据是过的，但是WA。 代码如下

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>

using namespace std ;

typedef long long lint ;
typedef long double dint ;

const lint MAXN = 1e6 + 5 ; // Next[] 长度
const lint MAXL1 = 1e6 + 5 ; // s1 长度
const lint MAXL2 = 1e6 + 5 ; // s2 长度

lint times ;
lint t1 , t2 ; // s1, s2 遍历到的下标
string s1, s2 ; // 文本串与模板串
lint lens1, lens2 ; // 文本串与模板串的长度

vector<lint> Next ; // Next[i]：S[0…i-1] 这个前缀的前缀后缀最大值
//vector<lint> place ; // 记录模板串在文本串上的位置
vector<lint> broder ; // 记录 broder 值

// 构建模板串 s2 的 next 数组
void get_Next(vector<lint> &Next, string &s, lint lens) {
	t1 = 0 ;
	Next[0] = t2 = -1 ;
	while (t1 < lens) {
		if (t2 == -1 || s[t1] == s[t2]) // 可以扩展匹配
			Next[++ t1] = ++ t2 ; // 扩展匹配
		else // 回退 t2，查找前缀中可能的匹配
			t2 = Next[t2] ;
	}
	return ;
}

// 判断模板串 s2 是否是文本串 s1 的子串
bool Kmp(vector<lint> &Next, string &s1, string &s2,  lint &lens1, lint &lens2) {
	t1 = 0, t2 = 0 ;
	while (t1 < lens1 && t2 < lens2) {
		// 当前字符匹配 或 处于模板串 s2 的第一个字符
		if (t2 == -1 || s1[t1] == s2[t2]) 
			t1 ++ , t2 ++ ; // 移动指针
		else // t2 回退
			t2 = Next[t2] ;
	}
	if (t2 == lens2) // 找到了匹配的子串
		return true ;
	else // 没有找到匹配
		return false ;
}

// 求模板串 s2 在文本串 s1 中出现了多少次
lint KMP(vector<lint> &Next, string &s1, string &s2,  lint &lens1, lint &lens2) {
	lint times = 0 ;
	t1 = 0, t2 = 0 ;
	while (t1 < lens1) {
		// 当前字符匹配 或 处于模板串 s2 的第一个字符
		if (t2 == -1 || s1[t1] == s2[t2]) 
			t1 ++ , t2 ++ ; // 移动指针
		else  // t2 回退
			t2 = Next[t2] ;
		if (t2 == lens2) { // 匹配成功
			times ++ ;
//			place.push_back(t1 - lens2 + 1) ;
			printf("%lld\n", t1 - lens2 + 1) ;
			t2 = Next[t2] ;
		}
	}
	return times ;
}

signed main() {
	
	// vector 初始化
	Next.resize(MAXN, 0) ;
	broder.resize(MAXL2, 0) ;
	
	// 输入
	getline(cin, s1) ;
	getline(cin, s2) ;
	lens2 = s2.size() ;
	lens1 = s1.size() ;
	
	// 处理
	get_Next(Next, s2, lens2) ;
	times = KMP(Next, s1, s2, lens1, lens2) ;
//	sort(place.begin() , place.end()) ;
	
	// 输出
//	for (lint i = 0 ; i < place.size() ; i ++)
//		cout << place[i] << '\n' ;
	for (int i = 1 ; i <= lens2 ; i ++) 
		cout << Next[i] << ' ' ;
	putchar('\n') ;
	
	return 0 ;
}