[SAM][多串][不同子串十进制求和][拓扑排序] hihocoder #1457 : 后缀自动机四·重复旋律7

https://hihocoder.com/problemset/problem/1457

要求求出来n个串中所有子串的十进制和。

考虑单个串的情况：顺着sam的边走的话，一个点的所有字串等于它所有的父节点的字串+c，c为从父节点转移来的路径字符，由十进制的性质可以知道当前节点（设为st）的和为则求出sam状态转移图的拓扑序然后刷sum即可；

多个串的情况：考虑把多个串合并为1个串，每两个串之间以‘9’+1填充（也就是: )，然后建立sam。此时要求出sam每个状态中有多少个不含：字符的子串，这里用到了一个性质就是，这个值恰好就是从初始状态S到状态st的所有”不经过冒号转移的边”的路径数目，而有向无环图上的路径数目也是一个经典的拓扑排序问题！

由此只需求拓扑序的过程中把有效子串个数求出来就行了。

wa点的话，注意第一次调用sam前要用init函数初始化。另外，拓扑排序无需纠结数据结构条件是指向父节点还是从父节点指向子节点。

#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=11;

struct sam_node
{
    sam_node * fa,*nxt[CHAR];
    int len;
    void clear()
    {
        fa=0;
        memset(nxt,0,sizeof(nxt));
    }
    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;
        }
    }
    return np;
}

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

LL cnt[maxn<<1];
int deg[maxn<<1];
int topsort[maxn<<1],t;
LL valid[maxn<<1];
LL ans[maxn<<1];

int Len;
void solve()
{
    sam_node* cur;
    int len=tail-pool;
    queue Q;
    for (int i=0; inxt[k])
                deg[cur->nxt[k]-pool]++;
    }

    for (int i=0; inxt[k])
            {
                dif=cur->nxt[k]-pool;
                deg[dif]--;
                if(!deg[dif])
                    Q.push(dif);
            }
    }
    //debug topsort
    //for (int i=0; inxt[k])
            {

                ans[cur->nxt[k]-pool]+=10*ans[topsort[i]]+k*valid[topsort[i]];
                valid[cur->nxt[k]-pool]+=valid[topsort[i]];
                if(ans[cur->nxt[k]-pool]>mod)
                    ans[cur->nxt[k]-pool]%=mod;
            }
    }
    LL res=0;
    for (int i=1; imod?res+ans[i]-mod:res+ans[i];
    printf("%lld\n",res);
}

int main()
{
    int N;
    scanf("%d",&N);
    getchar();
    scanf("%s",ori);
    Len=strlen(ori);
    sam_init();
    sam_node* pre=root,*cr;
    End[0]=root;
    int mi;
    for (mi=1; mi<=Len; mi++)
    {
        cr=extend(pre,ori[mi-1]-'0');
        pre=cr;
    }
    for (int i=2; i<=N; i++)
    {

        cr=extend(pre,10);
        pre=cr;
        scanf("%s",ori);
        Len=strlen(ori);
        for (int t=1; t<=Len; t++)
        {
            cr=extend(pre,ori[t-1]-'0');
            pre=cr;
        }
    }
    solve();

    return 0;
}

一	二	三	四	五	六	日
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30

发表回复 取消回复

发表回复取消回复