ans[1] = 1 的理解
查看原帖
ans[1] = 1 的理解
215368
Easy_revenge楼主2021/11/2 15:55

第一篇题解中提及的 ansans可以重叠的公共前后缀数量,而按此理解则会出现一个疑问:题目中的 nextinext_i 为对于前 ii 个字符构成的子串,既是它的后缀又是它的前缀的字符串中(它本身除外),最长的长度;那么所记录的公共前后缀自然也应满足本身除外的要求,这与标程中 ans1=1ans_1=1 相悖。

经巨佬苏铁的讲解,现提供一种更好的理解方式:
ansans 理解为从当前位置不断跳跃,跳到 00 所需的步数。那么首先 ans1=1ans_1=1 可以解释;对于末尾下标不为 11 的子串,它跳到 00 的步数显然就是它的 borderborder 数;对于仅由第 11 位构成的子串,在计算 numnum 没有符合要求的 borderborder

以上均为笔者理解,可能有误,望海涵。

2021/11/2 15:55
加载中...