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

tonyfang posted @ 2016年4月09日 21:02 in 随笔 with tags C++ OI , 1023 阅读
1、在 A 的子串中,不是 B的子串的字符串的数量。
2、在 A 的子串中,不是 B的子序列的字符串的数量。
3、在 A 的子序列中,不是 B的子串的字符串的数量。
4、在 A 的子序列中,不是 B的子序列的字符串的数量。
题解:对于 子串,采用 SAM,对于 子序列,采用 SAM。
# 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;
	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;

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;

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() {
	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;
} 说:
2023年6月18日 15:58

Our reporting team plans to provide the Education & Recruitment Update for all age groups and to present the actual picture of recent events through inside coverage. Our goal is to meet the needs of people of all ages by publishing news categorised as General, Political, Crime, Sports, Entertainment, Education, and World News.

登录 *

loading captcha image...
or Ctrl+Enter