又用后缀数组做了一遍。。。。

c要开很大才能过。。

Stammering Aliens

3
baaaababababbababbab
11
baaaababababbababbab
3
cccccc
0

5 12
none
4 2

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=40010;

int sa[maxn],rank[maxn],rank2[maxn],h[maxn],c[maxn],*x,*y,m;
char str[maxn];

void INIT()
{
    memset(sa,0,sizeof(sa));
    memset(rank,0,sizeof(rank));
    memset(rank2,0,sizeof(rank2));
    memset(h,0,sizeof(h));
    memset(c,0,sizeof(c));
}

bool cmp(int* r,int a,int b,int l,int n)
{
    if(r[a]==r[b]&&a+l<n&&b+l<n&&r[a+l]==r[b+l]) return true;
    return false;
}

void radix_sort(int n,int sz)
{
    for(int i=0;i<sz;i++) c[i]=0;
    for(int i=0;i<n;i++) c[x[y[i]]]++;
    for(int i=1;i<sz;i++) c[i]+=c[i-1];
    for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
}

void get_sa(char c[],int n,int sz=128)
{
    x=rank,y=rank2;
    for(int i=0;i<n;i++) x[i]=c[i],y[i]=i;
    radix_sort(n,sz);
    for(int len=1;len<n;len<<=1)
    {
        int yid=0;
        for(int i=n-len;i<n;i++) y[yid++]=i;
        for(int i=0;i<n;i++) if(sa[i]>=len) y[yid++]=sa[i]-len;

        radix_sort(n,sz);

        swap(x,y);
        x[sa[0]]=yid=0;

        for(int i=1;i<n;i++)
        {
            x[sa[i]]=cmp(y,sa[i],sa[i-1],len,n)?yid:++yid;
        }

        sz=yid+1;
        if(sz>=n) break;
    }
    for(int i=0;i<n;i++) rank[i]=x[i];
}


void get_h(char str[],int n)
{
    int k=0; h[0]=0x3f3f3f3f;
    for(int i=0;i<n;i++)
    {
        if(rank[i]==0) continue;
        k=max(k-1,0);
        int j=sa[rank[i]-1];
        while(i+k<n&&j+k<n&&str[i+k]==str[j+k]) k++;
        h[rank[i]]=k;
    }
}

bool ck(int L,int n)
{
    int len=0,temp=1;
    for(int i=1;i<=n;i++)
    {
        if(h[i]>=L) temp++;
        else
        {
            len=max(len,temp);temp=1;
        }
    }
    if(len>=m) return true;
    return false;
}

int doit(int L,int n)
{
    int ret=-1,temp=1,tt=sa[0];
    for(int i=1;i<=n;i++)
    {
        if(h[i]>=L)
        {
            temp++;
            tt=max(sa[i],tt);
        }
        else
        {
            if(temp>=m)
            {
                ret=max(ret,tt);
            }
            temp=1;tt=sa[i];
        }
    }
    return ret;
}

int main()
{
while(scanf("%d",&m)!=EOF&&m)
{
    INIT();
    scanf("%s",str);
    int n=strlen(str);
    get_sa(str,n);
    get_h(str,n);

    int low=1,high=n,mid,lenglengago=-1;

    while(low<=high)
    {
        mid=(low+high)/2;
        if(ck(mid,n)) lenglengago=mid,low=mid+1;
        else high=mid-1;
    }

    if(lenglengago==-1) puts("none");
    else
    {
        printf("%d %d\n",lenglengago,(m==1)?0:doit(lenglengago,n));
    }
}
    return 0;
}

HDOJ 4080 Stammering Aliens

原文：http://blog.csdn.net/u012797220/article/details/19554463