发布于 由itewqq

[SAM][最长公共子串][循环串] hihocoder #1465 : 后缀自动机五·重复旋律8

题意要求所有的T中的循环串在S中出现了多少次，多次出现重复计数。

先考虑处理循环串，我们可以把循环串往后复制一遍变成定长单串，这时候如果我们可以把处理定长单串的方法搞出来就也能搞出来循环了。现在考虑的是对于一个串T，以T[i]为结尾的长为n的串出现了几次。很容易想到用endpos的大小去求，所以应该先把endpos大小求出来，之后就是应该确定是哪个endpos。可以先考虑如何求出对于T[i]来说与S的最长公共子串，这时候只要在SAM上顺着fa树走一直到走到原点或者有可以往后转移就可以了。如果走到了根节点还是没有能转移的，那就说明就没有这个字符，直接全0就可以了。注意这时候的长度可能过大，也就是stl超过了n，而在计算的时候应该是只需要“刚刚好包含长度为n”的那个状态节点的endpos。所以需要再顺着fa往前跳到fa的len小于n就可以了。然后这时候还有一个重复计算的问题，这是由于循环串可能有重复产生的，这时候我们就得给同样的条件打上标记了，而怎么判断是同样的呢？显然当串相同的时候一定会走到相同的节点上，只需要在最后的+环节打标记就可以了。

wa点主要出在指针和状态下标的转换上以及数组的长度上，注意循环串要复制一遍的话得是2倍长度。。。emmm

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

using namespace std;
typedef long long LL;
const int maxn=100005;
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 hmn()
    {
        return len-fa->len;
    }
} pool[maxn<<1];

sam_node *root,*tail;//tail-root is how many nodes in sam

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;
            //nq->flag=1;//not include the prefix
            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];// raw string
sam_node *End[maxn];


int deg[maxn<<1];
int topsort[maxn<<1],t;//topsort data
int endpos[maxn<<1];//size of endpos

int Len;//ori's length

char T[maxn<<1];//error1
int vis[maxn<<1];//for the re-calculate

LL cal(int n)
{
    int tl=strlen(T);
    LL ans=0;
    int st=0,stl=0;
    sam_node* cur=pool;
    for (int i=0;inxt[cw])
            cur=cur->fa,stl=cur->len;//final error?
        if(cur->nxt[cw])
        {
            stl++;
            cur=cur->nxt[cw];
            st=cur-pool;
        }
        else
            st=0,stl=0,cur=pool;

        if(stl>n)
        {
            while(cur->fa->len>=n)
            {
                cur=cur->fa;
                stl=cur->len;
            }
        }
        st=cur-pool;//error2
        if(stl>=n&&!vis[st])
        {
            vis[st]=1;
            ans+=endpos[st];
        }
    }
    return ans;
}

void solve()
{
    sam_node* cur;
    int len=tail-pool;


    queue Q;
    for (int i=0; ifa)
            deg[cur->fa-pool]++;
    }

    for (int i=0; ifa)
        {
            deg[cur->fa-pool]--;
            if(!deg[cur->fa-pool])
                Q.push(cur->fa-pool);
        }
    }


    //get the endpos
    for (int i=0;iflag)
            endpos[topsort[i]]++;
        if(cur->fa)
        {
            endpos[cur->fa-pool]+=endpos[topsort[i]];
            //cout<fa-pool)<

发表回复

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

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