题意

给出每一个位置作为结尾,\(1\)作为开始的字符串的最小循环节长度,求字典序最小的字符串。

分析

首先两点KMP的结论,不给出证明了:

  •  长度为\(len\)字符串的最短循环节长度为\(len-Next[len]\)
  •  \(Next[i]\)表示\(i-1\)为结尾的字符串的最长公共前后缀(不算本身)

于是,如果当前的\(Next[i]\neq 0\),表示\(i-1\)位和\(Next[i]-1\)位相同。

如果当前位\(Next[i]=0\),显然对于所有的\(Next[i-1],Next[Next[i-1]],\cdots\)作为结尾的串的后一位都不能作为\(i-1\)位,判断一下可以放的最小的即可。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注