[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