我现在要抨击一下boshi大神的做法,真是不够优美......
一份优美的代码应该是短,便于看懂而且能够AC的,所以说.....干嘛啊。
寻找循环节,其实跑一遍kmp就够了,如果存在循环节的话,肯定是n-next[n]这个长度的前缀。
比如说ababab,next[6]=4嘛,所以是长度为2的前缀。但是有的时候,这个前缀不可以完全覆盖整个字符串,比如说ababa这个情况,那么答案就是1。
所以我们就可以得到一份精炼而优美的代码: