题目链接:
题目大意:给出一个字符串,依次左移一个单位形成一堆字符串,求其字典序最小和最大的字符串需要左移多少位,以及一共有几个这样的字符串(例如0101->1010->0101)。
解题思路:首先可以确定两个字符串出现的次数应该相同,即循环节数目,这个比较容易得到。然后就是最大最小字符串如何得到的问题了,直接暴力肯定超时。。。。
所以这里找到了比较好的方法,转载: by---cxlove
求字符串最小表示的方法
(1) 利用两个指针p1, p2。初始化时p1指向s[0], p2指向s[1]。
(2) k = 0开始,检验s[p1+k] 与 s[p2+k] 对应的字符是否相等,如果相等则k++,一直下去,直到找到第一个不同,(若k试了一个字符串的长度也没找到不同,则那个位置就是最小表示位置,算法终止并返回)。则该过程中,s[p1+k] 与 s[p2+k]的大小关系,有三种情况:
(A). s[p1+k] > s[p2+k],则p1滑动到p1+k+1处 --- 即s1[p1->p1+k]不会
是该循环字符串的“最小表示”的前缀。 k置为0
(B). s[p1+k] < s[p2+k],则p2滑动到p2+k+1处, k置为0
(C). s[p1+k] = s[p2+k],则 k++; if (k == len) 返回结果。
注:这里滑动方式有个小细节,若滑动后p1 == p2,将正在变化的那个指针再+1。直到p1、p2把整个字符串都检验完毕,返回两者中小于 len 的值。
(3) 如果 k == len, 则返回p1与p2中的最小值
代码
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 const int N=1e6+5; 7 8 int len; 9 int nxt[N];10 char p[N];11 12 void getnext(){13 int i,j;14 i=0,j=nxt[0]=-1;15 while(i 0) j+=k+1;35 else i+=k+1;36 }37 if(i==j) j++;38 k=0;39 }40 }41 return min(i,j)+1; //数组下标从0开始,题目是从1开始42 }43 44 int main(){45 while(~scanf("%s",p)){46 len=strlen(p);47 int min_idx=min_max_express(1);48 int max_idx=min_max_express(0);49 getnext();50 int mmin=len-nxt[len];51 int res=len%mmin?1:len/mmin;52 printf("%d %d %d %d\n",min_idx,res,max_idx,res);53 }54 return 0;55 }