hdu4333Revolving Digits

本文主要是介绍hdu4333Revolving Digits，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

依次将最后面的数字往第一位移动，求得出的这些结果中大于等于小于原数的个数；

解题思路：

为了保证结果的正确性，首先的去重，诸如123123这样的字符串，我们只要计算123这种情况即可，去重可以利用KMP求出循环节即可，最后将循环节复制成两份相同的再拓展kmp比较大小！

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int MAX=100000+10;
char s[MAX*2];
int next[MAX];
//kmp为了求循环节
void get_next(char *a,int len)
{int i=-1,j=0;next[0]=-1;while(j<len){if(i == -1 || a[i] == a[j])next[++j]=++i;elsei=next[i];}
}
//拓展kmp
void get_extend(char *a,int len)
{int k=0,i=1,maxr;next[0]=len;while(k+1<len && a[k] == a[k+1])++k;next[1]=k;k=1;while(++i<len/2){//只需要求到原串的长度即可maxr=k+next[k]-1;next[i]=min(next[i-k],max(maxr-i+1,0));while(i+next[i]<len && a[next[i]] == a[i+next[i]])++next[i];if(i+next[i]>k+next[k])k=i;}
}
int main(){int t,num=0;cin>>t;while(t--){scanf("%s",s);int len=strlen(s);get_next(s,len);int temp=len-next[len];if(len%temp!=0)temp=len;for(int i=0;i<=temp;++i)s[i+len]=s[i];get_extend(s,temp+temp);int a=0,b=0,c=0;for(int i=0;i<temp;++i){if(next[i]>=temp)++b;//表示等于原串的else if(s[next[i]]<s[i+next[i]])++c;//表示大于原串的else++a;//表示小于原串的}cout<<"Case "<<++num<<": "<<a<<' '<<b<<' '<<c<<endl;}return 0;
}

这篇关于hdu4333Revolving Digits的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---