[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