hdu3746cyclic专题

hdu3746Cyclic Nacklace

题目大意:        给你一串字符(a~b),问你最少需要在末尾添加多少个字符,使得这串字符形成一个循环,如abcab需要在末尾添加一个c即可. 解题思路: 其实就是next数组的应用。         当next[n]*2>=n的时候,必然出现了循环节,我们只要就出最小的循环节,pre=(n-(next[n]))然后,如果n%pre==0,的话就是说刚好形成的n/pre个循环,就不必