为什么这么写不会RE?
查看原帖
为什么这么写不会RE?
737158
yszkddzyh楼主2024/10/7 13:04

j=mj = m 时,访问 t[j+1]t[j + 1] 不会越界吗?为什么能 AC?

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
int n, m, nxt[N];
string s, t;

int main(){
	
	cin >> s >> t;
	int n = s.size(), m = t.size();
	s = " " + s, t = " " + t + " ";
	nxt[1] = 0;
	for(int i = 2, j = 0; i <= m; i++){
		while(j && t[i] != t[j + 1]) j = nxt[j];
		if(t[i] == t[j + 1]) j++;
		nxt[i] = j;
	}
	for(int i = 1, j = 0; i <= n; i++){
		while(j && s[i] != t[j + 1]) j = nxt[j];
		if(s[i] == t[j + 1]) j++;
		if(j == m){
			cout << i - m + 1 << endl;
		}
	}
	for(int i = 1; i <= m; i++)
		cout << nxt[i] << ' ';
	
	return 0;
}
2024/10/7 13:04
加载中...