/*注意注意：本题非hdu4333原题，而是简化版，原版有多组数据。但此代码在修改输入后依旧可以通过多组数据*/
给出一个数字串,问有多少本质不同同构串比原串小，一样,大.
同构串是指,对于原串S[1-N]通过旋转变成同构串S[i-N]+S[0-i-1].
本质不同,指的是字符串不一样.
输入格式：
一行一个数字串输出格式：
一行，输出本质不同的同构串比原串小，一样,大的三个数，用一个空格分隔开。样例输入：
123123
样例输出：
0 1 2
数据范围：
数字串长度<=100000首先，我们用KMP求得KMP中的next数组nex，这有什么用呢？其功能在于求出原字符串的循环节个数，以此保证计数的字符串本质不同
然后，设原字符串为s2，字符串s1=s2+s2。以s1为母串，s2为子串跑EKMP。
最后，对于每一个ex[i]，大于等于s2的长度即从第i个位置开始的组成的数与原数相等,否则只要比较s[i]与s[i+next[i]]（EKMP的next）。
#include<cstdio> #include<cstring> using namespace std; char s1[1000100],s2[1000100]; int ex[1000100],nxt[1000100],nex[1000100]; void get(char *s2){ int m=strlen(s2); nex[0]=nex[1]=0;int j=0; for(int i=1;i<m;i++){ while(j>0&&s2[i]!=s2[j])j=nex[j]; if(s2[i]==s2[j])j++; nex[i+1]=j; } } void getex(char *s2){ int j=0,n=strlen(s2); while(j+1<n&&s2[j+1]==s2[j])j++; nxt[0]=n;nxt[1]=j;int po=1,p=nxt[1]+1; for(int i=2;i<n;i++){ int len=nxt[i-po]; if(len+i<p)nxt[i]=len; else{ int j=p-i; if(j<0)j=0; while(i+j<n&&s2[j]==s2[j+i])j++; nxt[i]=j; po=i; p=nxt[po]+po; } } } void exkmp(char *s1,char *s2){ int j=0,n=strlen(s1),m=strlen(s2); while(s1[j]==s2[j]&&j<n&&j<m)j++; ex[0]=j;int po=0,p=ex[0]; for(int i=1;i<n;i++){ int len=nxt[i-po]; if(len+i<p)ex[i]=len; else{ int j=p-i; while(i+j<n&&j<m&&s1[j+i]==s2[j])j++; ex[i]=j; po=i; p=ex[po]+po; } } } int main(){ scanf("%s",s2);int len=strlen(s2); for(int i=0;i<len;i++) s1[i]=s2[i],s1[i+len]=s2[i]; getex(s2); exkmp(s1,s2); get(s2); int temp=len%(len-nex[len])==0?len/(len-nex[len]):1; int a=0,b=0,c=0; for(int i=0;i<len;i++){ if(ex[i]>=len)b++; else if(s1[i+ex[i]]<s2[ex[i]])a++; else c++; } printf("%d %d %d",a/temp,b/temp,c/temp); }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
