[SPOJ 220] | Eurce's Blog

后缀数组

给出最多10个字符串，每个字符串长度最多10,000，求这样一个子串的长度：
(1) 在每个字符串中非重叠地出现了两次；
(2) 长度最长。

可以将10个字符串连接在一起，其中每个连接位置用一个大于128的唯一值来隔开不同字符串，然后求后缀数组。随后，可以二分答案，对于某个长度值m，判断：对于h数组中值>=m的某连续区间内，求每个子串对应的原字符串最左和最右子串的位置，若每个字符串中左右子串的位置差>=m，即两个子串非重叠，return 1。而每次某区间内无法满足时，直接从该区间下一个位置开始检查h数组。由此对于每个长度值进行判断的时间复杂度是O(n)的，这里n是后缀数组的长度，最多100,000。总体时间复杂度便是O(nlgn)的。

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

#define M 100100

int t,n,b[M],r[M],sa[M],h[M],mxh,li[10],ri[10];
int d[M],wa[M],wb[M],wv[M],ws[M];
char s[M];

inline int cmp(int *r,int a,int b,int l)
{
    return r[a]==r[b]&&r[a+l]==r[b+l];
}
 
void da(int *r,int *sa,int n,int m)
{
    int i,j,p,*x=wa,*y=wb,*t;
    memset(ws,0,sizeof ws);
    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(j=1,p=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]];
        memset(ws,0,sizeof ws);
        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++;
    }
}

void init()
{
    int i,j,k,l;
    n=0;
    mxh=0;
    for(i=0;i<t;i++)
    {
        scanf("%s",s+n);
        l=strlen(s+n);
        mxh=max(mxh,l);
        for(j=n;j<n+l;j++)
        {
            b[j]=i;
            d[j]=s[j];
        }
        b[j]=i;
        d[j]=128+i;
        n+=l+1;
    }
    d[--n]=0;
    da(d,sa,n+1,max(n+1,228));
    for(i=0;i<n;i++)
        r[sa[i+1]]=i;
    for(i=0;i<n;i++)
        sa[r[i]]=i;
    for(i=k=0;i<n;i++)
    {
        if(!r[i])
            continue;
        for(j=sa[r[i]-1],k?k--:0;d[i+k]==d[j+k];k++);
        h[r[i]]=k;
    }
    n=n+1-t;
}

int calc(int m)
{
    int i,j,k,l;
    for(i=1;i<n;)
    {
        if(h[i]<m)
        {
            i++;
            continue;
        }
        memset(li,127,sizeof li);
        memset(ri,-1,sizeof ri);
        li[b[sa[i-1]]]=min(li[b[sa[i-1]]],sa[i-1]);
        ri[b[sa[i-1]]]=max(ri[b[sa[i-1]]],sa[i-1]);
        for(j=i;h[j]>=m;j++)
        {
            li[b[sa[j]]]=min(li[b[sa[j]]],sa[j]);
            ri[b[sa[j]]]=max(ri[b[sa[j]]],sa[j]);
        }
        for(k=0;k<t;k++)
        {
            if(ri[k]-li[k]<m)
                break;
        }
        if(k==t)
            return 1;
        i=j;
    }
    return 0;
}

void solve()
{
    int i,j,k,l,h,m;
    for(l=0,h=mxh;l<h;)
    {
        m=l+h+1>>1;
        if(calc(m))
            l=m;
        else
            h=m-1;
    }
    printf("%d\n",l);
}

int main()
{
    scanf("%*d");
    while(~scanf("%d",&t))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define M 100100

int t,n,b[M],r[M],sa[M],h[M],mxh,li[10],ri[10];

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

char s[M];

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

{

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

}

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

{

int i,j,p,*x=wa,*y=wb,*t;

memset(ws,0,sizeof ws);

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(j=1,p=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]];

memset(ws,0,sizeof ws);

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++;

}

void init()

{

int i,j,k,l;

n=0;

mxh=0;

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

{

scanf("%s",s+n);

l=strlen(s+n);

mxh=max(mxh,l);

for(j=n;j<n+l;j++)

{

b[j]=i;

d[j]=s[j];

}

b[j]=i;

d[j]=128+i;

n+=l+1;

}

d[--n]=0;

da(d,sa,n+1,max(n+1,228));

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

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

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

sa[r[i]]=i;

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

{

if(!r[i])

continue;

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

h[r[i]]=k;

}

n=n+1-t;

}

int calc(int m)

{

int i,j,k,l;

for(i=1;i<n;)

{

if(h[i]<m)

{

i++;

continue;

}

memset(li,127,sizeof li);

memset(ri,-1,sizeof ri);

li[b[sa[i-1]]]=min(li[b[sa[i-1]]],sa[i-1]);

ri[b[sa[i-1]]]=max(ri[b[sa[i-1]]],sa[i-1]);

for(j=i;h[j]>=m;j++)

{

li[b[sa[j]]]=min(li[b[sa[j]]],sa[j]);

ri[b[sa[j]]]=max(ri[b[sa[j]]],sa[j]);

}

for(k=0;k<t;k++)

{

if(ri[k]-li[k]<m)

break;

}

if(k==t)

return 1;

i=j;

}

return 0;

}

void solve()

{

int i,j,k,l,h,m;

for(l=0,h=mxh;l<h;)

{

m=l+h+1>>1;

if(calc(m))

l=m;

else

h=m-1;

}

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

}

int main()

{

scanf("%*d");

while(~scanf("%d",&t))

{

init();

solve();

}

return 0;

}

很好的题目……这题也是罗穗骞论文里推荐的最后一道例题了。虽然还是没太看懂他的DA和DC3，不过确实学到了很有趣的知识。

ps：也推荐一个最近发现的汽车网站：38号测试中心。