并不对劲的spoj1811

题意是求两个字符串的lcs，两个串都只包含小写字母。

本题既可以用后缀自动机，又可以用后缀数组。

对于后缀自动机，就是一道模板题，直接对于一个字符串建后缀自动机再用另一个串查询就行。

对于后缀数组，其实也是一道模板题，但不是后缀数组的模板，而是用后缀数组求同一字符串的两个后缀的最长公共前缀的模板。

用h(x)表示排序前在第x位的后缀s1与排序后排在s1前一位的s2（记为prev(x)）的最长公共前缀。

这样就会发现这些性质：

1.想要求出排序前位于k1,k2的后缀的最长公共前缀，只需要（用后缀数组）找出它们在排序后的位置，再求区间最值就可以。

2.对于排序前位于k的后缀s，它和所有排序后在它前面后缀的最长公共前缀不会超过h(k)。

根据性质2，会发现可以将两个用一个奇怪的字符连成一个大串，再对这个大串求后缀数组。这样，对于所有满足x与prev(x)在奇怪的字符异侧的h(x)求最大值就可以了。

那么问题又来了，如何快速求h(x)?

直接比较显然是不行的。经过一番并不对劲的考虑，发现h(x)>=h(x-1)-1。这是因为h(x-1)表示第x-1位的后缀和第prev(x-1)位的后缀的最长公共前缀，而第x位的后缀相当于是将第x-1位后缀最前面的字符去掉后形成的。那么，将第prev(x-1)位的后缀最前面的字符去掉，得到的字符串也是后缀之一（可能为空），而且它与第x位的后缀的最长公共前缀是h(x-1)-1。也就是说，第x位的后缀在排序后前面存在一个后缀与它的最长公共前缀是h(x-1)-1。根据性质2，就可以得出h(x)>=h(x-1)-1了。这样就能大大地减少了复杂度。

感觉这题还是用后缀自动机更方便。

#include<iostream>

#include<iomanip>

#include<cmath>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<queue>

#define maxn 500010

using namespace std;

inline int read()

{

    int xx=,ff=;

    char ch=getchar();

    while(isdigit(ch)==&&ch!='-')ch=getchar();

    if(ch=='-')ff=-,ch=getchar();

    while(isdigit(ch))xx=xx*+ch-'',ch=getchar();

    return xx*ff;

}

void write(int x)

{

    int ff=;char ch[];

    if(x<)

    {

        x=-x;

        putchar('-');

    }

    while(x)ch[++ff]=(x%)+'',x/=;

    if(ff==)putchar('');

    while(ff)putchar(ch[ff--]);

    putchar(' ');

}

int sa[maxn],ord[maxn],x[maxn],n,m=;

int y[maxn],c[maxn],h[maxn];

char s[maxn];

void get_sa()

{

    memset(x,,sizeof(x));

    memset(y,,sizeof(y));

    memset(c,,sizeof(c));

    for (int i=;i<n;i++) c[x[i]=s[i]]++;

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

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

    for (int k=;k<=n;k<<=)

    {

        int p = ;

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

        for (int i=;i<n;i++) if (sa[i] >= k) y[p++] = sa[i] - k;

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

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

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

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

        swap(x,y);

        p = ;

        x[sa[]] = ;

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

            x[sa[i]]= (y[sa[i-]]==y[sa[i]]&&y[sa[i-]+k]==y[sa[i]+k])?p-:p++;

        if (p>=n) break;

        m=p;

    }

}

void getheight()

{

    int i,j,k=;

    memset(h,,sizeof(h));

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

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

    {

        if(k) k--;

        if(ord[i]==)continue;

        j=sa[ord[i]-];

        while(s[i+k]==s[j+k]) k++;

        h[i]=k;

    }

}

int main()

{

    char s2[maxn];

    scanf("%s",s);

    int split=strlen(s);

    scanf("%s",s2);

    strcat(s,"A");

    strcat(s,s2);

    n=strlen(s);

    get_sa();

    getheight();

    int maxx=;

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

    {

        if((sa[i]>split&&sa[i-]<split)||(sa[i-]>split&&sa[i]<split))

        {

            maxx=max(maxx,h[sa[i]]);

        }

    }

    write(maxx);

    return ;

}

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#define maxn 250010

using namespace std;

int ans,len,p;

int read()

{

    int f=,x=;char ch=getchar();

    while(isdigit(ch)== && ch!='-')ch=getchar();

    if(ch=='-')f=-,ch=getchar();

    while(isdigit(ch))x=x*+ch-'',ch=getchar();

    return x*f;

}

void write(int x)

{

    int ff=;char ch[];

    while(x)ch[++ff]=(x%)+'',x/=;

    if(ff==)putchar('');

    while(ff)putchar(ch[ff--]);

    putchar(' ');

}

typedef struct node

{

    int to[],dis,fa;

}spot;

struct SAM

{

    spot x[maxn*];

    int cnt,rt,lst;

    char s[maxn];

    void start()

    {

        lst=rt=++cnt;

        scanf("%s",s+);

        int ls=strlen(s+);

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

            extend(i);

    }

    void extend(int pos)

    {

        int val=s[pos]-'a',p=lst,np=++cnt;

        lst=np,x[np].dis=pos;

        for(;p&&x[p].to[val]==;p=x[p].fa)x[p].to[val]=np;

        if(p==)x[np].fa=rt;

        else

        {

            int q=x[p].to[val];

            if(x[q].dis==x[p].dis+)x[np].fa=q;

            else

            {

                int nq=++cnt;

                x[nq].dis=x[p].dis+;

                memcpy(x[nq].to,x[q].to,sizeof(x[q].to));

                x[nq].fa=x[q].fa,x[np].fa=x[q].fa=nq;

                for(;x[p].to[val]==q;p=x[p].fa)x[p].to[val]=nq;

            }

        }

    }

}t;

int main()

{

    char s2[maxn];

    t.start();

    scanf("%s",s2+);

    int ls2=strlen(s2+);

    p=t.rt;

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

    {

        int val=s2[i]-'a';

        if(t.x[p].to[val])len++,p=t.x[p].to[val];

        else

        {

            while(p&&t.x[p].to[val]==)p=t.x[p].fa;

            if(p==)p=t.rt,len=;

            else len=t.x[p].dis+,p=t.x[p].to[val];

        }

        ans=max(ans,len);

    }

    write(ans);

    return ;

}

SAM

巴特西

并不对劲的spoj1811

最新文章

热门文章