【hdu4436】str2int

2015.06.16 20:30 Tue | 29次阅读 | 旧日oi | 固定链接 | 源码

题目大意:给出n个数字,数字很长,用字符串读入,长度总和为10^5。求这n个字符串的所有子串(不重复)的和取模2012 。
题解:通过这道题有点搞明白各种更新关系了……
把串变成数字,都连起来,中间用10分割(这样省空间),然后建立后缀自动机,并对len基数排序。对于一个节点p,如果有son[p][i]不等于0,那么p就可以更新son[p][i]的答案,怎么更新呢,首先是把能到p的值的总和乘10,然后加上能到达p的路径数*当前枚举的i,然而这个路径数是怎么回事呢,不应该就是1么?并不是这样,因为节点是被压缩的,所以可能这个点有多个状态,那么是len[p]-len[fa[p]]么?也不是,因为可能存在无法到达的问题,所以这个路径数是需要记录的,并且值始终在1到len[p]-len[fa[p]]之间。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 250005
#define mod 2012
int n,len;
char ts[200005];
int a[N];
struct SAM
{
    int len[N],son[N][11],fa[N];
    int cnt[N],sum[N],v[N],rk[N];
    int last,tot,ans;
    void init()
    {
        last=tot=1;ans=0;
        memset(son,0,sizeof(son));memset(v,0,sizeof(v));
        memset(cnt,0,sizeof(cnt));memset(sum,0,sizeof(sum));
    }
    void insert(int x)
    {
        int p=last,np=++tot;last=np;
        len[np]=len[p]+1;
        for(;p&&!son[p][x];p=fa[p]) son[p][x]=np;
        if(!p) fa[np]=1;
        else
        {
            int q=son[p][x];
            if(len[q]==len[p]+1) fa[np]=q;
            else 
            {
                int nq=++tot;len[nq]=len[p]+1;
                memcpy(son[nq],son[q],sizeof(son[q]));
                fa[nq]=fa[q];fa[q]=fa[np]=nq;
                for(;p&&son[p][x]==q;p=fa[p]) son[p][x]=nq;
            }
        } 
    }
    void solve(int L)
    {
        for(int i=1;i<=tot;i++) v[len[i]]++;
        for(int i=1;i<=L;i++) v[i]+=v[i-1];
        for(int i=tot;i;i--) rk[v[len[i]]--]=i;
        cnt[1]=1;
        for(int i=1;i<=tot;i++)
        {
            int k=rk[i];
            for(int j=(i==1);j<10;j++)
            {
                if(son[k][j])
                {
                    int t=son[k][j];
                    cnt[t]=(cnt[t]+cnt[k])%mod;
                    sum[t]=(sum[t]+sum[k]*10%mod+cnt[k]*j%mod)%mod;
                }
            }
            ans=(ans+sum[k])%mod;
        }
        printf("%d\n",ans);
    }
}sam;
int main()
{   
    while(cin>>n)
    {
        sam.init();len=0;
        for(int tl,i=1;i<=n;i++)
        {
            scanf("%s",ts);tl=strlen(ts);
            for(int j=0;j<tl;j++) 
            {
                a[len]=ts[j]-'0';
                sam.insert(a[len++]);
            }
            a[len]=10;sam.insert(a[len++]);
        }
        sam.solve(len);
    }
}```