你不对劲
查看原帖
你不对劲
1305692
xiangixuan楼主2025/6/16 18:38

第一篇题解对 ai,ca_{i, c} 的解释是:

在每个位置记录 ai,ca_{i, c},表示 sai,c+1=cs_{a_{i, c}+1}=c 且能使 [ai,c+1,i][a_{i, c}+1, i] 成为合法子串的最大的下标。

但代码中:

a[to[i]][s[i]-'a']=i;

带回解释,区间是:[i+1,toi][i+1, to_i] .

显然 toiito_i \leq i ,左边界大于右边界,解释有误.

ai,ca_{i, c} 正确的解释应该是:

在每个位置记录 ai,ca_{i, c},表示若 toj=ito_j=i ,则 sai,c+1=cs_{a_{i, c}+1}=c 且能使 [ai,c+1,j][a_{i, c}+1, j] 成为合法子串的最大的下标。

2025/6/16 18:38
加载中...