hdu4436-str2int（后缀数组 or 后缀自动机）

时间：2021-08-30 12:13:41

题意：给你一堆字符串，仅包含数字'0'到'9'。

例如 101 123

有一个字符串集合S包含输入的N个字符串，和他们的全部字串。

操作字符串很无聊，你决定把它们转化成数字。

你可以把一个字符串转换成一个十进制整数。

如果一个数字出现了多次，只留一个。

计算所有数字的和，模2012。

1<=N<=10000

题解：参考 http://blog.csdn.net/kqzxcmh/article/details/8122747

每个后缀的所有前缀就是所有子串。sa[i]和sa[i-1]有height[i]的长度是重复的，可以不考虑。

把字符串连起来，中间加分隔符，构成一个大的字符串，然后整体求后缀数组。

对于一个字符串123
可以v[0]=1 v[1]=12 v[3]=123  v[i]是0-i构成的数字
sum是前缀和 sum[0]=1 sum[1]=13 sum[2]=136

对于后缀23 sum[2]-sum[0] 得到 12+123的和

对于12需要减去10 对于123需要减去100

所以求l~r 首先需要sum[r]-sum[l-1], 然后设x=r-l

需要减去 for(int i=1;i<=x;++i) pow(10, i);

可以预处理出来。

太难辣！！像我这种辣鸡不适合这么难的题T^T

时限3s，187ms还是比较快的。

//后缀数组

#include <stdio.h>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

const int N = int(2e5)+;

const int M = ;

int cmp(int *r,int a,int b,int l){

    return (r[a]==r[b]) && (r[a+l]==r[b+l]);

}

// 用于比较第一关键字与第二关键字,

// 比较特殊的地方是,预处理的时候,r[n]=0(小于前面出现过的字符)

int wa[N],wb[N],wss[N],wv[N];

int sa[N];          // 排第i的是谁 i:1~n sa:0~n-1

int rk[N],          // i排第几 i:0~n-1 rk:1~n

    height[N];      // 排名相邻的两个后缀的最长公共前缀长度:suffix(sa[i-1])和(sa[i]) 的最长公共前缀，

char str[N];

void DA(char *r,int *sa,int n,int m){                    // 此处N比输入的N要多1，为人工添加的一个字符，用于避免CMP时越界 m是不同的字符的个数

    int i,j,p,*x=wa,*y=wb,*t;

    for(i=;i<m;i++) wss[i]=;

    for(i=;i<n;i++) wss[x[i]=r[i]]++;

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

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

    for(j=,p=;p<n;j*=,m=p)

    {

        for(p=,i=n-j;i<n;i++) y[p++]=i;

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

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

        for(i=;i<m;i++) wss[i]=;

        for(i=;i<n;i++) wss[wv[i]]++;

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

        for(i=n-;i>=;i--) sa[--wss[wv[i]]]=y[i];

        for(t=x,x=y,y=t,p=,x[sa[]]=,i=;i<n;i++)

            x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;

    }

}

void calheight(char *r,int *sa,int n){                    // 此处N为实际长度

    int i,j,k=;

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

    for(i=;i<n; height[rk[i++]] = k )

    for(k?k--:,j=sa[rk[i]-]; r[i+k]==r[j+k]; k++);

}

char word[N];

int d[N];   // 该字符串的结束位置

int sum[N];

int v[N];

int Pow[N];

int cal(int l, int r) {

    if (l > r) return ;

    //printf(">>%d %d %d %d %d\n", l, r, sum[r+1], sum[l], v[l]);

    //printf("%d\n", ((sum[r+1]-sum[l]) - v[l]*Pow[r-l+1]%M + M) % M);

    return ((sum[r+]-sum[l]) - v[l]*Pow[r-l+]%M + M) % M;

}

int main(int argc, char const *argv[])

{

    //freopen("in.txt", "r", stdin);

    Pow[]=;Pow[]=;

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

        Pow[i]=(Pow[i-]+)*%M;

    int n;

    while (~scanf("%d", &n)) {

        int idx = ;

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

            scanf("%s", word);

            int len = strlen(word);

            int val = ;

            for (int j = ; j < len; ++j) {

                str[idx] = word[j] - '' + ;

                val = (val *  + str[idx] - ) % M;

                v[idx+] = val; //+1是因为会有-1 <0很麻烦= =

                sum[idx+] =  (sum[idx] + val) % M;

                d[idx] = len - j + idx;

                idx++;

            }

            d[idx] = idx;

            sum[idx+] = v[idx+] = ;

            str[idx++] = ; //1~11

        }

        str[idx] = ;

        DA(str, sa, idx+, );

        calheight(str, sa, idx);

        int ans = ;

        for (int i = ; i < idx; ++i) {

            if (str[i] ==  || str[i] == ) continue;  // 不要前导零

            int l = i + height[rk[i]];//重复的部分

            int r = d[i]-;

            //printf("i=%d,l=%d, r=%d\n", i, l, r);

            if (l > r) continue;

            ans = (ans + cal(i, r) - cal(i, l-)) % M;

            //ans = (ans + cal(l, r)) % M; 这个不对 因为所求字符串是从i开始的

            ans = (ans + M) % M;

        }

        printf("%d\n", ans);

    }

    return ;

}

后缀自动机= = 先留坑吧orz。。。。

相关文章