hdu3518

题解：

后缀数组

枚举长度为k(1<=k<=len/2)的满足要求的子串个数

代码：

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=;

char str[N];

int wa[N],wb[N],wv[N],Ws[N],sa[N],Rank[N],height[N];

int cmp(int *r,int a,int b,int l)

{

    return r[a]==r[b]&&r[a+l]==r[b+l];

}

void da(const char *r,int *sa,int n,int m)

{

    int *x=wa,*y=wb,*t;

    for (int i=;i<m;i++) Ws[i]=;

    for (int i=;i<n;i++) Ws[x[i]=r[i]]++;

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

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

    for (int j=,p=;p<n;j*=,m=p)

     {

         p=;

        for (int i=n-j;i<n;i++) y[p++]=i;

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

         if (sa[i]>=j) y[p++]=sa[i]-j;

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

        for (int i=;i<m;i++) Ws[i]=;

        for (int i=;i<n;i++) Ws[wv[i]]++;

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

        for (int i=n-;i>=;i--) sa[--Ws[wv[i]]]=y[i];

        swap(x,y);x[sa[]]=;p=;

        for (int i=;i<n;i++)x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;

     }

    return;

}

void calheight(const char *r,int *sa,int n)

{

    int j,k=;

    for (int i=;i<=n;i++) Rank[sa[i]]=i;

    for (int i=;i<n;height[Rank[i++]]=k)

     for (k?k--:,j=sa[Rank[i]-];r[i+k]==r[j+k];k++);

    return;

}

int solve(int k,int len)

{

    int maxx=,minn=INT_MAX,ans=;

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

     {

        if (height[i]>=k)

         maxx=max(maxx,max(sa[i-],sa[i])),minn=min(minn,min(sa[i-],sa[i]));

         else

          {

            if (maxx-minn>=k) ans++;

            maxx=,minn=INT_MAX;

          }

     }

    if (maxx-minn>=k)ans++;

    return ans;

}

int main()

{

    while (~scanf("%s",str) && strcmp(str,"#")!=)

     {

        int len=strlen(str);

        da(str,sa,len+,);

        calheight(str,sa,len);

        ll ans=;

        for (int i=;i<=len/;i++)ans+=solve(i,len);

        printf("%d\n",ans);

     }

    return ;

}