[POJ 3415] | Eurce's Blog

后缀数组

给出两个长度最多100,000的字符串s和t，求s和t中所有长度大于K的相同子串配对数。

做法首先是将s[sl]置最大值，并将t放在s[sl]后，计算后缀数组。接下来需要顺序遍历h[n]，遍历到位置i时，如果sa[i]属于s，那么找出0到i-1中所有属于t且与s公共后缀长度>=m的子串，并将累计的配对数记录以类似计数排序的方式记录为ab[n]中，sa[i]对应满足题意的配对总数即为ab[h[i]]。如果sa[i+1]也属于s，且h[i+1]>=h[i]，那么sa[i+1]对应的配对数和sa[i]是相同的；若h[i+1]<h[i]，那么也能根据ab[h[i+1]]来O(1)地得到结果。

这里在更新ab[n]时本来应该是分成ab[2][n]，分别对属于s和属于t的后缀分别维护配对总数的，这样根据平摊分析构造ab的总时间复杂度就是O(n)，但实现起来细节太多了容易错。而现在这种偷懒的做法会导致当sa[i]、sa[i+1]、sa[i+2]……分别属于s、t、s……且都满足h[]>=m时，需要反复重新计算ab，但这种情况实际上较少出现，所以并不会慢上太多。

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

#define ll long long
#define M 200002

int sl,n,m,r[M],sa[M],h[M],ei[M];
int d[M],wa[M],wb[M],wv[M],ws[M];
char s[M],b[M];
ll ans,ab[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;
    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(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]];
        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++;
    }
}

void init()
{
    memset(ab,0,sizeof ab);
    int i,j,k,l;
    ans=0;
    scanf("%s",s);
    sl=strlen(s);
    s[sl]=126;
    scanf("%s",s+sl+1);
    n=sl+1+strlen(s+sl+1);
    for(i=0;i<=n;i++)
        d[i]=s[i];
    da(d,sa,n+1,max(128,n+1));
    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;s[i+k]==s[j+k];k++);
        h[r[i]]=k;
    }
    for(i=0;i<n;i++)
    {
        if(sa[i]<sl)
            b[i]=0;
        else
            b[i]=1;
    }
}

void solve()
{
    int i,j,k,l;
    for(i=1,k=0;i<n;i++)
    {
        if(b[i-1]!=b[i])
        {
            k=h[i];
            for(j=0;j<=h[i];j++)
                ab[j]=0;
            for(j=i,l=h[j];j&&l>=m&&h[j]>=m;)
            {
                if(b[j-1]!=b[i])
                    ab[l]++;
                j--;
                l=min(l,h[j]);
            }
            for(j=h[i]-1;j>=m;j--)
                ab[j]+=ab[j+1];
            for(j=m+1;j<=h[i];j++)
                ab[j]+=ab[j-1];
        }
        else
            k=min(k,h[i]);
        ans+=ab[k];
    }
    printf("%lld\n",ans);
}

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

100

101

102

103

104

105

106

107

108

109

110

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define M 200002

int sl,n,m,r[M],sa[M],h[M],ei[M];

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

char s[M],b[M];

ll ans,ab[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;

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(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]];

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

}

void init()

{

memset(ab,0,sizeof ab);

int i,j,k,l;

ans=0;

scanf("%s",s);

sl=strlen(s);

s[sl]=126;

scanf("%s",s+sl+1);

n=sl+1+strlen(s+sl+1);

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

d[i]=s[i];

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

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;s[i+k]==s[j+k];k++);

h[r[i]]=k;

}

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

{

if(sa[i]<sl)

b[i]=0;

else

b[i]=1;

}

void solve()

{

int i,j,k,l;

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

{

if(b[i-1]!=b[i])

{

k=h[i];

for(j=0;j<=h[i];j++)

ab[j]=0;

for(j=i,l=h[j];j&&l>=m&&h[j]>=m;)

{

if(b[j-1]!=b[i])

ab[l]++;

j--;

l=min(l,h[j]);

}

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

ab[j]+=ab[j+1];

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

ab[j]+=ab[j-1];

}

else

k=min(k,h[i]);

ans+=ab[k];

}

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

}

int main()

{

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

{

init();

solve();

}

return 0;

}

ps：上周刚赶完第二篇论文，以为可以稍微轻松点了，结果马上又被安排写专利…… 总不会到时候真的让我写第三篇吧？

ps2：另外，最近也在看毛姆的《月亮和六便士》。