后缀数组的应用 hdu 3518

这两天一直再看后缀数组，虽然很难，但渐渐有一点感觉了，越来越觉height数组真的非常强大，做hdu3518题基本毫不费力；

题意大致是求一个字符串中不相交的重复子串的总数，思想大致是穷尽每一个长度i（最长是字符的一半），再看每一个height数组中的值是否大于i，注意连续时表示是同一字符串，比如，aaaa，当i为1时,就有height[2]=1;height[3]=2;表示a，aa，这里是重复的，要处理一下，下面是我的代码：

/*******************************************************************************/
/* OS           : Linux fc20.x86_64 #1 SMP Tue Dec  UTC 2013 x86_64  GNU/Linux
 * Compiler     : 4.8.2 20131212 (Red Hat 4.8.2-7) (GCC)
 * Encoding     : UTF8
 * Date         : 2014-04-02
 * All Rights Reserved by alop.
*****************************************************************************/
/* Description: ***************************************************************
*****************************************************************************/
/* Analysis: ******************************************************************
*****************************************************************************/
/*****************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<string>
using namespace std;
#define N 1010
#define INF 0x7f7f7f
int WA[N],WB[N],WV[N],WS[N];
int 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(char *r,int *sa,int n,int m)
{
    int i,j,p,*x=WA,*y=WB,*t;
    for(i=0; i<m; i++) WS[i]=0;
    for(i=0; i<n; i++) WS[x[i]=r[i]]++;
    for(i=1; i<m; i++) WS[i]+=WS[i-1];
    for(i=n-1; i>=0; i--) sa[--WS[x[i]]]=i;
    for(p=1,j=1; p<n; j*=2,m=p)
    {
        for(p=0,i=n-j; i<n; i++) y[p++]=i;
        for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0; i<n; i++) WV[i]=x[y[i]];
        for(i=0; i<m; i++) WS[i]=0;
        for(i=0; i<n; i++) WS[WV[i]]++;
        for(i=1; i<m; i++) WS[i]+=WS[i-1];
        for(i=n-1; i>=0; i--) sa[--WS[WV[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
    return ;
}
void calheight(char *r,int *sa,int n)
{
    int i,j,k=0;
    for(i=1; i<=n; i++)Rank[sa[i]]=i;
    for(i=0; i<n; height[Rank[i++]]=k)
        for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
    return;
}
char str[N];
int s[N],sa[N];

int main()
{

    while(scanf("%s",str)&&str[0]!=‘#‘)
    {
        int siz=strlen(str);
        da(str,sa,siz+1,128);
        calheight(str,sa,siz);
        int Max,Min,ans=0;
        for(int i=1;i<=(siz+1)/2;i++)
        {
            Min=INF;Max=-1;
            for(int j=1;j<=siz;j++)
            {
                if(height[j]>=i)
                {
                    int tmp=sa[j]>sa[j-1]?sa[j]:sa[j-1];
                    Max=Max>tmp?Max:tmp;
                     tmp=sa[j]<sa[j-1]?sa[j]:sa[j-1];
                    Min=Min<tmp?Min:tmp;

                }
                else
                {
                    if(Min+i<=Max)
                        ans++;
                    Min=INF;
                    Max=-1;
                }
            }
            if(Min+i<=Max)
                ans++;
       }
        cout<<ans<<endl;
    }
   return 0;
}

后缀数组的应用 hdu 3518,布布扣,bubuko.com

后缀数组的应用 hdu 3518

原文：http://blog.csdn.net/alop_daoyan/article/details/24542975