[KMP+最小示意法]hdoj 3374:String Problem
[KMP+最小表示法]hdoj 3374:String Problem
大致题意:
给出一个字符串,求出其第一个最小表示和最大表示的位置,并分别求出最小表示的个数和最大表示的个数。
大致思路:
最小表示法+KMP扩展出的最小重复子串,一顿乱搞即可。本来打算用后缀数组,但是看数据量达到了1000000,还是作罢了~~囧
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int nMax=1000005; char pat[nMax]; int lenp,next[nMax]; void get_next(){ int i,j=-1; next[0]=-1; for(i=1;i<=lenp;i++){ //pat[j]是不是可以理解为i的前一个字符的next值所指想的字符 while(j>-1&&pat[j+1]!=pat[i])j=next[j]; if(pat[j+1]==pat[i])j++; next[i]=j; } } //最小表示 int minexp(char *s,int x) { int i=0,j=1,k=0,t; while(i<x&&j<x&&k<x) { t=s[(i+k)%x]-s[(j+k)%x]; if(t==0) k++; else { if(t>0) i+=k+1; else j+=k+1; if(i==j) j++; k=0; } } return i<j?i:j; } //最大表示 int maxexp(char *s,int x) { int i=0,j=1,k=0,t; while(i<x&&j<x&&k<x) { t=s[(i+k)%x]-s[(j+k)%x]; if(t==0) k++; else { if(t<0) i+=k+1; //这里是区别 else j+=k+1; if(i==j) j++; k=0; } } return i<j?i:j; } int main(){ int ans,i,j,a,b; while(scanf("%s",pat)!=EOF){ lenp=strlen(pat); get_next(); a=minexp(pat,lenp); b=maxexp(pat,lenp); int l=(lenp-1)-next[lenp-1]; if(lenp%l==0){ ans=lenp/l;//cout<<lenp/l<<endl;; } else{ ans=1;//printf("1\n"); } printf("%d %d %d %d\n",a+1,ans,b+1,ans); } return 0; } //h 3374