出发前的稍作准备,复习一部分知识点
KMP的next数组的部分性质:
(以下均默认下标从1开始)
next[i]: 以i结尾的后缀中与其匹配的最大前缀的长度。
对于一个长度为l的字符串s,其最短循环节长度为:l-next[l]
如果\(i\)%\((i-next[i])==0\),那么\(s[1\sim (i-next[i])]\) 为\(s[1\sim i]\)的最小循环元,\(i/(i-next[i])\)为该循环元的循环次数。
咕。
标签:前奏,next,循环,长度,远航,序曲,sim From: https://www.cnblogs.com/int-Hello-world/p/17566950.html