题意:给定一个数字x(x<=105),不停得把数字得最后几位放到最前面去。求最多可以产生多少中不同得数字,求出这些数字与原数字比较大于、等于、小于的个数。

思路:每一个可能得数字就是:将原字符串自身复制一遍之后在其中截取的一段,其长度等于原数字长。 我们可以借助倍增、DC_3或者扩展KMP求出复制后每个后缀与原字符串的最长公共前缀长度。(受限于本题的时间限制和数据范围,倍增光荣牺牲)设X为原串自我复制一次后的字符串。如果X的后缀A和原字符串X的最长公共前缀长度为k,那么比较A和X的大小就只需要比较A[k]和X[k]。这样就可以在O(lenX)时间内求出:X的每个长度为len的后缀和X的大小关系。 需要注意的是:如果X的后缀A和X的最长公共前缀长度k>=lenX/2,那么我们就人为X和A相等。因为真正生成的数字只是A的前lenX/2位。

还有一个问题:如何处理字符串重复的问题?自己多写几个样例就会发现:字符串重复的次数总是等于原字符串的循环节数。证明:如果将串Ab经过移动变为bA,且Ab==bA,那么




依此类推。

所以每发生一次Ab==bA(b尽可能短),则原串的循环节数就会多一。同理推知,原串有w个循环节则会发生w次Ab==bA。因为原串有w个循环节,所以对于每个循环节中的第i个数字b[i],如果它在操作时出现在串的末尾,那么一定会对应一个不同答案。又因为有w个循环节,所以每个答案出现了w次,所以只需要将答案数除以w即可。w可以结合kmp的next数组在O(n)时间复杂度内求出。

在这里推荐几扩展(拓展)kmp的教程:

教程1
教程2