HDU 4162 Shape Number

题目链接：

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

题意：

求给定字符的一阶差分链的最小表示。

题解：

先求一阶差分链，再求一阶差分链的最小表示法。

代码：

跑了670MS

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn = 3e5 + ;

char s1[maxn],s2[maxn];

int solve(char *s) {

    int i = , j = , k = ,len=strlen(s);

    while (i < len&&j < len&&k<len) {

        int t = s[(i + k) % len] - s[(j + k) % len];

        if (!t) k++;

        else {

            if (t > ) i = i + k + ;

            else j = j + k + ;

            if (i == j) j++;

            k = ;

        }

    }

    return i < j ? i : j;

}

int main() {

    while (scanf("%s", s1) == ) {

        int len = strlen(s1);

        for (int i = ; i < len; i++) {

            s2[i] = (s1[(i + ) % len] - s1[i] + ) %  + '';

        }

        s2[len] = '\0';

        //cout << s2 << endl;

        int pos = solve(s2);

        for (int i = ; i < len; i++) {

            printf("%c", s2[(pos + i) % len]);

        }

        printf("\n");

    }

    return ;

}

贴个后缀数组的解法：

跑了2527MS

#include<map>

#include<cmath>

#include<queue>

#include<vector>

#include<cstdio>

#include<string>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define mid (l+(r-l)/2)

#define sz() size()

#define pb(v) push_back(v)

#define all(o) (o).begin(),(o).end()

#define clr(a,v) memset(a,v,sizeof(a))

#define bug(a) cout<<#a<<" = "<<a<<endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;

const LL INFL=0x3f3f3f3f3f3f3f3fLL;

const double eps=1e-;

const int maxn = 3e5 + ;

char s1[maxn],s2[maxn];

struct SuffixArray{

    char s[maxn];

    int sa[maxn],t[maxn],t2[maxn],c[maxn];

    int n,m;

    void init(int n,int m){

        this->n=n;

        this->m=m;

    }

    void build_sa(){

        int i,*x=t,*y=t2;

        for(i=;i<m;i++) c[i]=;

        for(i=;i<n;i++) c[x[i]=s[i]]++;

        for(i=;i<m;i++) c[i]+=c[i-];

        for(i=n-;i>=;i--) sa[--c[x[i]]]=i;

        for(int k=;k<=n;k<<=){

            int p=;

//            for(i=n-k;i<n;i++) y[p++]=i;

//            for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;

            for(i=;i<n;i++) y[p++]=(sa[i]-k+n)%n;

            for(i=;i<m;i++) c[i]=;

            for(i=;i<n;i++) c[x[y[i]]]++;

            for(i=;i<m;i++) c[i]+=c[i-];

            for(i=n-;i>=;i--) sa[--c[x[y[i]]]]=y[i];

            swap(x,y);

            p=; x[sa[]]=;

            for(i=;i<n;i++){

                x[sa[i]]=y[sa[i-]]==y[sa[i]]&&y[sa[i-]+k]==y[sa[i]+k]?p-:p++;

            }

            if(p>=n) break;

            m=p;

        }

    }

}mysa;

int main() {

    while (scanf("%s", s1) == ) {

        int len = strlen(s1);

        mysa.init(len,);

        for (int i = ; i < len; i++) {

            s2[i] = (s1[(i + ) % len] - s1[i] + ) %  + '';

        }

        s2[len] = '\0';

        strcpy(mysa.s,s2);

        mysa.build_sa();

        for(int p=mysa.sa[];p<mysa.sa[]+mysa.n;p++){

            printf("%c",mysa.s[p%mysa.n]);

        }

        puts("");

    }

    return ;

}