本文共 1453 字，大约阅读时间需要 4 分钟。

链接：

题目大意：

给一个数字字符串S，  可以把S最后一个数字移动到最前面变成另一个数字。例如123，  经过移动依次变成312，231，123。 注意当移动次数正好和S长度相等时，S又变回了最开始的那个数字。

求这个移动过程所形成的所有字符串，大于S（最初的）的数字，等于S，以及小于S的各有多少个。

分析与总结：

1. 首先要考虑以怎样的形式保存S，因为以往题目一般的移动方式都是最左边的数字移动到最右边的，只需要复制2倍的即可。 而这题是把最右边的移动到最左边的，也可以这样处理。虽然它是最右边的移到最左边的，但是我们可以逆过来想，从最终状态变为就初状态，就相当于“恢复”的过程：把最左边的数字移动到最右边。

2. 然后是枚举起点比较。如果朴素的方法复杂度为O（n^2），肯定超时，所以要想到用一个线性时间的方法。

    再仔细一看，发现其实就是裸的拓展KMP了：设原来字符串为T， 长度为len， 那么复制两倍后的为S， S的前len个数就是最初的数字。接下来求T的所有后缀与T的最长公共长度。求这个，是为了节省比较的时间，假设有两个字符串aabbde, aaberf，那么已经知道了前面三个数字是相同的了，只需要比较第4个数即可。 这样，比较只需要O(1)的复杂度即可。那么总的复杂度就是O(n).

3. 这题还要考虑去重的情况，可能移动的过程会有多个相同的数字。之所以会有多个相同的数，是因为有循环节。所以只需要求出最小循环节，枚举这最小循环节之内的情况即可。

4. 拓展KMP求最短循环节的方法：

// 已经求出next数组int kk;  // kk保存最短循环节for(int i=1; i<=len; ++i){    if(i+next[i]>=len){        kk = len%i ? len : i;        break;    }}

代码：

#include
   
    #include
    
     #include
     
      using namespace std;const int MAXN = 10^100000*2; char S[MAXN];int  f[MAXN];void getNext(char* T, int* next){    int len=strlen(T), a=0;    next[0] = len;    while(a
      
       = p){            int j = max(p-k+1, 0);            while(k+j
       
        =len){                kk = len%i ? len : i;                break;            }        }        for(int i=0; i
        
         =len) ++E; else if(f[i]>0 && f[i]
         
           S[f[i]]) ++G; else ++L; } else if(f[i]==0){ if(S[i]>S[0]) ++G; else ++L; } } printf("Case %d: %d %d %d\n",cas++,L,E>0,G); } return 0;}
         
        
       
      
     
    
   

          原创  ， By   D_Double  (转载请标明)