当 j=m 时,访问 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;
}