HDU 3374 String Problem(最小最大表示法+KMP)

链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3374

题目大意：

给定一个字符串S， 可以通过向左移位得到另一个字符串。例如，S="SKYLONG", 通过位移得到的所有字符串（后面的数字表示rank，即第几个）：

SKYLONG 1
KYLONGS 2
YLONGSK 3
LONGSKY 4
ONGSKYL 5
NGSKYLO 6
GSKYLON 7

求出一个字符串经位移后的所有字符串中字典序最小和字典需最大的rank，以及他们出现的次数。

分析与总结：

经过分析，很快可以得到大概的思路：

1. 把S复制成2倍

2. 找出字典序最小和最大的字符串

3. 直接KMP求出他们的次数即可。

关键在于第二步。 第一次做时直接枚举，结果TLE了。势必要用一个效率更高的方法找到字典序最小和最大的字符串。

经过百度得知这个方法就是“最小最大表示法”。

资料：

【浅析“最小表示法”思想在字符串循环同构问题中的应用--03 周源】：1.论文 2.ppt

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 1000005;
char S[MAXN*2];
char first[MAXN];
char last[MAXN];
int  rank_first, rank_last;
int  next[MAXN];

void getNext(char* S,int* next){
    int n=strlen(S);
    next[0]=next[1]=0;
    for(int i=1; i<n; ++i){
        int j=next[i];
        if(j && S[i]!=S[j]) j=next[j];
        next[i+1] = S[i]==S[j]?1+j:0;
    }
}

int find(char* S,char* P,int* next){
    getNext(P,next);
    int n=strlen(S);
    int m=strlen(P);
    int j=0;
    int cnt=0;
    for(int i=0; i<n; ++i){
        while(j && S[i]!=P[j]) j=next[j];
        if(S[i] == P[j]) ++j;
        if(j==m){
            ++cnt;
        }
    } 
    return cnt;
}
//最小表示法
void getMin(char* S){
    int i=0, j=1;
    int len=strlen(S);
    len >>= 1;
    while(i<len && j<len){
        int k=0;
        while(k<len && S[i+k]==S[j+k]) 
            ++k;
        if(k >= len)
            break;
        if(S[i+k] > S[j+k])
            i = max(i+k+1,j+1);
        else
            j = max(i+1,j+k+1);
    }
    int pos=min(i,j);
    rank_first=pos+1;
    for(int i=0; i<len; ++i)
        first[i] = S[pos++];
    first[len] = '\0';
}
//最大表示法
void getMax(char* S){
    int i=0, j=1;
    int len=strlen(S);
    len >>= 1;
    while(i<len && j<len){
        int k=0;
        while(k<len && S[i+k]==S[j+k]) 
            ++k;
        if(k >= len)
            break;
        if(S[i+k] < S[j+k])
            i = max(i+k+1,j+1);
        else
            j = max(i+1,j+k+1);
    }
    int pos=min(i,j);
    rank_last=pos+1;
    for(int i=0; i<len; ++i)
        last[i] = S[pos++];
    last[len] = '\0';
}
    
    
int main(){
    while(scanf("%s",S)!=EOF){
        int len=strlen(S);
        for(int i=0; i<len; ++i){
            S[len+i] = S[i];
        }
        S[2*len] = '\0';
        // 先找到字典需最小的和最大的排位
        getMin(S);
        getMax(S);
        printf("%d %d %d %d\n",rank_first,find(S+1,first,next),rank_last,find(S+1,last,next));
    }   
    return 0;
}

—— 生命的意义，在于赋予它意义士。

原创http://blog.csdn.net/shuangde800，By D_Double (转载请标明)