「为什么要hash才能KMP」 - 洛谷帖子保存站

为什么要hash才能KMP

板块P10475 [USACO03FALL] Milking Grid（数据加强版）
楼主Schrochanshun
当前回复0
已保存回复0
发布时间2025/2/5 17:48
上次更新2025/2/5 17:51:05

被骇客银狼阻止的越权访问保存失败

为什么要hash才能KMP

Schrochanshun楼主2025/2/5 17:48

如果用每一行最小循环节长度的lcm与每一列最小循环节长度的lcm相乘求解，就看看以下数据 $AAAABAA \\ AAABAAA$

你会发现存在某一个数( $5$ )小于当前每一行中最小循环节长度构成的lcm( $5\times 4=20$ )，这个数可以作为所有列在横向方向上的最小循环节长度,最后答案是 $5\times 2=10$

通常情况中的KMP，只是求得一行/一列的字符串的最小循环节长度。为了考虑到所有行/列，把字符串的每一列映射成一个数字，可以保证求得所有列在横向方向上的最小循环节长度。同理再去求所有行在纵向方向上的最小循环节长度，然后两者相乘得解。

2025/2/5 17:48