发布于 由itewqq

[SAM][拓扑排序][计算endpos大小] hihocoder 1449 : 后缀自动机三·重复旋律6

http://hihocoder.com/problemset/problem/1449

需要在O(n)时间内求出所有长度为k的字串中出现次数最多的字串的出现次数。这里的话首先肯定是要求出来endpos的大小了，球的方法是利用fa树上的不同的st之间的包含关系和子树之间的交集为空的性质。这样的话要想求出来某个点的endpos大小只需要知道它的子节点的endpos大小就行了，另外还有一种需要特判的情况就是当st包含S的前缀的时候需要再额外+1，因为这个前缀是后面的节点没有包含到的。

推的过程的话，首先求出来拓扑序，然后从后往前刷fa节点的cnt即可。但是如果就这样的话，要用朴素的算法求出来每个substring的长度还是需要n²的复杂度，仍然会卡住。然后这里有一个性质那就是长度短的substring中的最大值一定不会比长度长的小，然后我们只需要更新每个节点对应的maxlen的最大值就可以了，然后从后往前更新最大值。为什么这么做是对的？首先每个st里最大值那个点肯定是对的，然后每两个更新点之间的那一段一定是被某个右端点包含在内的一个st里的连续的一段，所以这些点其实和那个右端点的大小其实是一样的，刷过去肯定是对的。

#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;
typedef long long LL;
const int maxn=1000005;
const int mod=1e9+7;
const int CHAR=26;

struct sam_node
{
    sam_node * fa,*nxt[CHAR];
    int len;
    bool flag;
    //LL cnt;
    void clear()
    {
        fa=0;
        flag=0;
        memset(nxt,0,sizeof(nxt));
        //cnt=0;
    }
    int cnt()
    {
        return len-fa->len;
    }
} pool[maxn<<1];

sam_node *root,*tail;

sam_node* newnode(int len)
{
    sam_node* cur=tail++;
    cur->clear();
    cur->len=len;
    return cur;
}

void sam_init()
{
    tail=pool;
    root=newnode(0);
}

sam_node* extend(sam_node* last,int x)
{
    sam_node *p=last,*np=newnode(p->len+1);
    while(p&&!p->nxt[x])
        p->nxt[x]=np,p=p->fa;
    if(!p)
        np->fa=root;
    else
    {
        sam_node* q=p->nxt[x];
        if(q->len==p->len+1)
            np->fa=q;
        else
        {
            sam_node* nq=newnode(p->len+1);
            memcpy(nq->nxt,q->nxt,sizeof(q->nxt));
            nq->fa=q->fa;
            q->fa=np->fa=nq;
            while(p&&p->nxt[x]==q)
                p->nxt[x]=nq,p=p->fa;
        }
    }
    np->flag=1;
    return np;
}

char ori[maxn];
sam_node *End[maxn];

LL cnt[maxn<<1];
int deg[maxn<<1];
int topsort[maxn<<1],t;
LL ans[maxn];
int Len;
void solve()
{
    sam_node* cur;
    int len=tail-pool;
    queue Q;
    for (int i=1; ifa-pool]++;
    }
    for (int i=1; ifa-pool;
        deg[dif]--;
        if(!deg[dif]&&dif)
            Q.push(dif);
    }
    for (int i=len-1; i; i--)
    {
        int x=topsort[i];
        cur=pool+x;
        if(cur->flag)
            cnt[x]++;
        if(cur->fa)
            cnt[cur->fa-pool]+=cnt[x];
    }
    for (int i=1; ilen]=max(ans[cur->len],cnt[i]);
    }
    for (int i=Len-1; i; i--)
    {
        ans[i]=max(ans[i],ans[i+1]);
    }
}

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //gets(ori);
    scanf("%s",ori);
    Len=strlen(ori);
    sam_init();
    End[0]=root;
    for (int i=1; i<=Len; i++)
    {
        End[i]=extend(End[i-1],ori[i-1]-'a');
    }
    solve();
    for (int i=1; i<=Len; i++)
        printf("%lld\n",ans[i]);
    return 0;
}
/*

*/

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用 Akismet 来减少垃圾评论。了解我们如何处理您的评论数据。