[POJ 2406] | Eurce's Blog

后缀数组（？）

题意是，给出一个最长1,000,000的字符串，求该字符串是否为某子串的完全重复，并输出最大的重复数。

……之前敲的快排二倍增完全没有任何AC的希望，贴了个基排二倍增TLE依旧，随后又颤抖着贴了一份DC3……2938ms刚好卡过……：

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

#define M 2000010
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)

char s[M];
int n,d[M],sa[M],r[M],h[M];
int wa[M],wb[M],wv[M],ws[M];

int c0(int *r,int a,int b)
{
    return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];
}

int c12(int k,int *r,int a,int b)
{
    if(k==2)
        return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
    else
        return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];
}

void sort(int *r,int *a,int *b,int n,int m)
{
     int i;
     for(i=0;i<n;i++) wv[i]=r[a[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--) b[--ws[wv[i]]]=a[i];
     return;
}

void dc3(int *r,int *sa,int n,int m)
{
    int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
    r[n]=r[n+1]=0;
    for(i=0;i<n;i++)
        if(i%3!=0) wa[tbc++]=i;
    sort(r+2,wa,wb,tbc,m);
    sort(r+1,wb,wa,tbc,m);
    sort(r,wa,wb,tbc,m);
    for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)
        rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
    if(p<tbc) dc3(rn,san,tbc,p);
    else for(i=0;i<tbc;i++) san[rn[i]]=i;
    for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3;
    if(n%3==1) wb[ta++]=n-1;
    sort(r,wb,wa,ta,m);
    for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i;
    for(i=0,j=0,p=0;i<ta && j<tbc;p++)
        sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
    for(;i<ta;p++) sa[p]=wa[i++];
    for(;j<tbc;p++) sa[p]=wb[j++];
    return;
}

void init()
{
    n=strlen(s);
    memset(d,0,sizeof d);
    memset(sa,0,sizeof sa);
    memset(r,0,sizeof r);
    memset(h,0,sizeof h);
    int i,j,k,l;
    for(i=0;i<n;i++)
        d[i]=s[i]-'a'+1;
    dc3(d,sa,n+1,max(128,n+1));
    for(i=1;i<=n;i++)
        r[sa[i]]=i-1;
    for(i=0;i<n;i++)
        sa[r[i]]=i;
    for(i=k=0;i<n;i++)
    {
        if(!r[i])
            continue;
        for(k?k--:0,j=sa[r[i]-1];r[i]&&s[i+k]==s[j+k];k++);
        h[r[i]]=k;
    }
    memset(s,0,sizeof s);
}

void solve()
{
    int i=n-h[r[0]];
    if(!r[0]||!h[r[0]]||h[r[0]]-h[r[i]]!=i||n%i)
    {
        puts("1");
        return;
    }
    printf("%d\n",n/i);
}

int main()
{
    while(~scanf("%s",s))
    {
        if(s[0]=='.'&&!s[1])
            break;
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define M 2000010

#define F(x) ((x)/3+((x)%3==1?0:tb))

#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)

char s[M];

int n,d[M],sa[M],r[M],h[M];

int wa[M],wb[M],wv[M],ws[M];

int c0(int *r,int a,int b)

{

return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];

}

int c12(int k,int *r,int a,int b)

{

if(k==2)

return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);

else

return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];

}

void sort(int *r,int *a,int *b,int n,int m)

{

int i;

for(i=0;i<n;i++) wv[i]=r[a[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--) b[--ws[wv[i]]]=a[i];

return;

}

void dc3(int *r,int *sa,int n,int m)

{

int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;

r[n]=r[n+1]=0;

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

if(i%3!=0) wa[tbc++]=i;

sort(r+2,wa,wb,tbc,m);

sort(r+1,wb,wa,tbc,m);

sort(r,wa,wb,tbc,m);

for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)

rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;

if(p<tbc) dc3(rn,san,tbc,p);

else for(i=0;i<tbc;i++) san[rn[i]]=i;

for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3;

if(n%3==1) wb[ta++]=n-1;

sort(r,wb,wa,ta,m);

for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i;

for(i=0,j=0,p=0;i<ta && j<tbc;p++)

sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];

for(;i<ta;p++) sa[p]=wa[i++];

for(;j<tbc;p++) sa[p]=wb[j++];

return;

}

void init()

{

n=strlen(s);

memset(d,0,sizeof d);

memset(sa,0,sizeof sa);

memset(r,0,sizeof r);

memset(h,0,sizeof h);

int i,j,k,l;

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

d[i]=s[i]-'a'+1;

dc3(d,sa,n+1,max(128,n+1));

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

r[sa[i]]=i-1;

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

sa[r[i]]=i;

for(i=k=0;i<n;i++)

{

if(!r[i])

continue;

for(k?k--:0,j=sa[r[i]-1];r[i]&&s[i+k]==s[j+k];k++);

h[r[i]]=k;

}

memset(s,0,sizeof s);

}

void solve()

{

int i=n-h[r[0]];

if(!r[0]||!h[r[0]]||h[r[0]]-h[r[i]]!=i||n%i)

{

puts("1");

return;

}

printf("%d\n",n/i);

}

int main()

{

while(~scanf("%s",s))

{

if(s[0]=='.'&&!s[1])

break;

init();

solve();

}

return 0;

}

虽然罗穗骞神牛号称DC3实现得很精简……但是……这压行也太严重了吧……反正我是没怎么看懂……

另外贴一个之前自己写的KMP：

#include<cstdio>
#include<cstring>

int sl,p[1000000],d[1000000];
char s[1000001];

int main()
{
	int i,j,k,l;
	while(~scanf("%s",s))
	{
		sl=strlen(s);
		if(sl==1&&s[0]=='.') break;
		p[0]=-1;
		d[0]=1;
		for(i=1,j=-1;i<sl;i++)
		{
			while(j!=-1&&s[i]!=s[j+1]) j=p[j];
			if(s[i]==s[j+1]) j++;
			if(j!=-1&&i==j+(j+1)/d[j]) d[i]=d[j]+1;
			else d[i]=1;
		}
		printf("%d\n",d[sl-1]);
	}
	return 0;
}

#include<cstdio>

#include<cstring>

int sl,p[1000000],d[1000000];

char s[1000001];

int main()

{

int i,j,k,l;

while(~scanf("%s",s))

{

sl=strlen(s);

if(sl==1&&s[0]=='.') break;

p[0]=-1;

d[0]=1;

for(i=1,j=-1;i<sl;i++)

{

while(j!=-1&&s[i]!=s[j+1]) j=p[j];

if(s[i]==s[j+1]) j++;

if(j!=-1&&i==j+(j+1)/d[j]) d[i]=d[j]+1;

else d[i]=1;

}

printf("%d\n",d[sl-1]);

}

return 0;

}

同样是O(n)的复杂度，却只跑了219ms。

总感觉后缀数组是重剑无锋呢，现在的功力要驾驭实在是比较吃力……