UVA1673 str2int

UVA1673 str2int

题意

多组数据，每次给出n个均由整数构成的字符串，将每个字符串的所有子串转化成整数，去重并求和。

题解

首先将n个字符串拼接起来，中间用符号（如":"）隔开，将问题转化成求新串中本质不同的子串的和，那么我们就可以用后缀自动机完成。
定义cnt[v]为从初始状态到状态v的不同方法数（其中不含有前导零和分隔符）。sum[v]表示从初始状态到状态v的所有数字之和。
先将后缀自动机的所有节点根据len进行计数排序，然后从后向前进行转移，转移方程如下：
cnt[v]=\(\sum\)cnt[u]（u是v的父亲，即从u可以到v）
sum[v]=\(\sum\)cnt[u]*10+cnt[u]*i(u是v的父亲)

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
#define Clr(x) memset(x, 0, sizeof x)

struct state{
	int len,link;
	int nxt[30];
}st[N<<1];
int sz,last;

void sam_init(){
	Clr(st);
	st[0].len=0;
	st[0].link=0;
	sz=1;
	last=1;
} 

void sam_extend(char c){
	int cur=++sz;
	st[cur].len=st[last].len+1;
	int p=last;
	while(p&&!st[p].nxt[c-‘0‘]){
		st[p].nxt[c-‘0‘]=cur;
		p=st[p].link;
	}
	if(!p){
		st[cur].link=1;
	}else{
		int q=st[p].nxt[c-‘0‘];
		if(st[p].len+1==st[q].len){
			st[cur].link=q;
		}else{
			int clone=++sz;
			st[clone]=st[q];
			st[clone].len=st[p].len+1;
			while(p&&st[p].nxt[c-‘0‘]==q){
				st[p].nxt[c-‘0‘]=clone;
				p=st[p].link;
			}
			st[q].link=st[cur].link=clone;
		}
	}
	last=cur;
}

int ind[N],rk[N];
int cnt[N],sum[N];
const int mod=2012;
int ans,len;

void solve(){
	memset(ind,0,sizeof(ind));
	memset(cnt,0,sizeof(cnt));
	memset(sum,0,sizeof(sum));
	memset(rk,0,sizeof(rk));
	for(int i=1;i<=sz;i++) ind[st[i].len]++;
	for(int i=1;i<=len;i++) ind[i]+=ind[i-1];
	for(int i=1;i<=sz;i++) rk[ind[st[i].len]--]=i;
	
	cnt[1]=1;
	for(int i=1;i<=sz;i++){
		int x=rk[i];
		for(int j=0;j<10;j++){
			if(i==1&&j==0) continue;
			int p=st[x].nxt[j];
			cnt[p]=(cnt[p]+cnt[x])%mod;
			sum[p]=(sum[p]+sum[x]*10+j*cnt[x])%mod;
		}
		ans=(ans+sum[x])%mod;
	}
}

char s[N];
int t;

int main(){
	while(scanf("%d",&t)!=EOF){
		sam_init();
		ans=0;
		len=0;
		for(int i=1;i<=t;i++){
			if(i!=1) sam_extend(10+‘0‘),len++;
			scanf("%s",s+1);
			int n=strlen(s+1);
			for(int j=1;j<=n;j++){
				sam_extend(s[j]),len++;
			}
		}
		solve();
		printf("%d\n",ans);
	}
	return 0;
} 

UVA1673 str2int

原文：https://www.cnblogs.com/qjy73/p/12621239.html