做一个高产的菜鸡
传送门: HDU - 3374
题意: 多组输入, 给你一个字符串, 求它最小和最大表示法出现的位置和次数.
题解: 刚刚学会最大最小表示法, amazing.. 次数就是最小循环节循环的次数.
- #include<bits/stdc++.h>
- using namespace std;
- int nt[1000100],b[1000100];
- char a[1000100];
- void kmp_nt(int m)
- {
- int i,j;
- i = 0;
- nt[0] = j =-1;
- while(i <m){
- while(j!=-1&&a[i]!=a[j])
- j = nt[j];
- if(a[i]==a[j]||j==-1){
- i++;
- j++;
- nt[i]=j;
- }
- }
- }
- int Getmin(char s[])
- {
- int n = strlen(s);
- int i = 0,j = 1,k = 0,t;
- // 表示从 i 开始 k 长度和从 j 开始 k 长度的字符串相同
- while(i<n&&j<n&&k<n){
- t = s[(i+k)%n]-s[(j+k)%n];
- //t 用来计算相对应位置上那个字典序较大
- if(!t) k++;// 字符相等的情况
- else{
- if(t>0) i+=k+1;//i 位置大, 最大表示法: j += k+1
- else j+=k+1;//j 位置大, 最大表示法: i += k+1
- if(i==j) j++;
- k=0;
- }
- }
- return i>j?j:i;
- }
- int GetMax(char s[]){
- int len = strlen(s);
- int i=0,j=1,k=0;
- while(i<len&&j<len&&k<len){
- int t=s[(i+k)%len]-s[(j+k)%len];
- if(t==0)k++;
- else{
- if(t>0)j=j+k+1;
- else i=i+k+1;
- if(i==j)j++;
- k=0;
- }
- }
- return i<j?i:j;
- }
- int main()
- {
- while(scanf("%s",a)!=EOF){
- int len=strlen(a);
- kmp_nt(len);
- int k=1;
- int ans=len-nt[len];
- if(len%ans==0) k=len/ans;
- int mi=Getmin(a);
- int ma=GetMax(a);
- cout<<mi+1<<''<<k<<' '<<ma+1<<' '<<k<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3477651.html