FJOI2016Training 公共串问题 【序列自动机+后缀自动机】

tonyfang posted @ 2016年4月09日 21:02 in 随笔 with tags C++ OI , 315 阅读
1、在 A 的子串中,不是 B的子串的字符串的数量。
2、在 A 的子串中,不是 B的子序列的字符串的数量。
3、在 A 的子序列中,不是 B的子串的字符串的数量。
4、在 A 的子序列中,不是 B的子序列的字符串的数量。
题解:对于 子串,采用 SAM,对于 子序列,采用 SAM。
不要问我为啥都用SAM
因为一个是SeqAM,一个是SufAM。
# include <stdio.h>

using namespace std;

const int M=4010, Ms=26, Mod=998244353;
struct AM {
	int root, ch[M][Ms], tot, cnt[M];
};
struct SeqAM: public AM {
	int head[Ms], next[M];
	SeqAM() {
		tot = root = 1;
		for (int i=0; i<Ms; ++i) head[i] = tot;	
	}
	inline void insert(char c) {
		++tot, next[tot]=head[c];
		for (int i=0; i<Ms; ++i)
			for (int j=head[i]; j && !ch[j][c]; j=next[j]) ch[j][c]=tot;
		head[c]=tot;
	}
	inline void getcnt() {
		for (int i=1; i<=tot; ++i) cnt[i] = 1;
		for (int i=tot; i>=1; --i)
			for (int j=0; j<Ms; ++j) cnt[i] += cnt[ch[i][j]], cnt[i] %= Mod;
	}
}SEA, SEB;

struct SufAM: public AM {
	int fail[M], last, len[M], cl;
	SufAM() {tot=last=root=1, cl=0;}
	inline void insert(char c) {
		++tot, ++cl;
		int x=tot, p=last;
		last=x, len[x] = cl;
		for (;p && !ch[p][c]; p=fail[p])
			ch[p][c] = x;
		if(!p) fail[x] = root;
		else if(len[ch[p][c]] == len[p]+1)
			fail[x] = ch[p][c];
		else {
			int child = ch[p][c], cm = ++tot;
			len[cm] = len[p]+1;
			fail[cm] = fail[child];
			for (int i=0; i<Ms; ++i)
				ch[cm][i] = ch[child][i];
			fail[child] = fail[x] = cm;
			for (;ch[p][c] == child; p=fail[p]) ch[p][c] = cm;
		}
	}
	int s1[M], s[M];
	inline void getcnt() {
		for (int i=0; i<M; ++i) s[i]=0;
		for (int i=1; i<=tot; ++i) s[len[i]]++;
		for (int i=1; i<M; ++i) s[i]+=s[i-1];
		for (int i=1; i<=tot; ++i) s1[s[len[i]]--]=i;
		for (int i=1; i<=tot; ++i) cnt[i] = 1;
		for (int i=tot; i>=1; --i)
			for (int j=0; j<Ms; ++j)
				cnt[s1[i]] += cnt[ch[s1[i]][j]], cnt[s1[i]] %= Mod;
	}
}SUA, SUB;


int dp[M][M];
AM *cura, *curb;
int dfs(int a, int b) {
	if(!a) return 0;
	if(!b) return cura->cnt[a];
	if(dp[a][b] >= 0) return dp[a][b];
	int ans=0;
	for (int i=0; i<Ms; ++i) 
		ans += dfs(cura->ch[a][i],curb->ch[b][i]), ans%=Mod;
	return dp[a][b] = ans;
}
int get(AM &a, AM &b) {
	cura = &a, curb = &b;
	for (int i=1; i<=a.tot;++i)
		for (int j=1; j<=b.tot;++j)
			dp[i][j] = -1;
	dfs(a.root, b.root);
	return (dp[a.root][b.root]+Mod)%Mod;
}

char A[M], B[M];
int main() {
	scanf("%s%s",A,B);
	for (int i=0; A[i]; ++i) SEA.insert(A[i]-'a'), SUA.insert(A[i]-'a');
	for (int i=0; B[i]; ++i) SEB.insert(B[i]-'a'), SUB.insert(B[i]-'a');
	SEA.getcnt(), SEB.getcnt(), SUA.getcnt(), SUB.getcnt();
	int AUBU=get(SUA, SUB), AEBE=get(SEA, SEB), AEBU=get(SEA, SUB), AUBE=get(SUA, SEB);
	printf("%d\n%d\n%d\n%d\n", AUBU, AUBE, AEBU, AEBE);
	
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter