关于Hash后才能KMP的原因
查看原帖
关于Hash后才能KMP的原因
676591
Schrochanshun楼主2025/2/5 18:51
  1. 如果用每一行最小循环节长度的lcm与每一列最小循环节长度的lcm相乘求解，就看看以下数据 AAAABAAAAABAAAAAAABAA \\ AAABAAA
  • 你会发现存在某一个数(55)小于当前每一行中最小循环节长度构成的lcm( 5×4=205\times 4=20 )，同时小于字符矩阵中每一行的长度，因此这个数可以作为字符矩阵所有列在横向方向上的最小循环节长度,最小单位面积是5×2=105×2=10
  1. 通常情况下的KMP，只是求得一行/一列的字符串的最小循环节长度(∣s∣−next[∣s∣]\vert s \vert-next[\vert s \vert])。为了考虑到所有行/列，把字符矩阵的每一列映射成一个数字，可以求得字符矩阵所有列在横向方向上的最小循环节长度aa，之后把字符矩阵的每一行映射成一个数字，去求字符矩阵所有行在纵向方向上的最小循环节长度bb，这个过程相当于把二维降为一维，a×ba\times b 即为最小单位面积。
2025/2/5 18:51