"蔚来杯"2022牛客暑期多校训练营9 - G. Magic Spells (PAM)

Magic Spells

原题指路:https://ac.nowcoder.com/acm/contest/33194/G

题意

给定$k(1\le k\le 5)k\backslash \; \backslash \; (1\backslash leq\; k\backslash leq\; 5)$个长度之和不超过$3\mathrm{e}53\backslash mathrm\{e\}5$且只包含小写字母的字符串,求它们本质不同的公共回文子串的个数.

思路

对第一个串建PAM,剩下的串同建Trie树的方式插入PAM的Trie树中.$cnt[i][j]cnt[i][j]$表示第$ii$个字符串是否有以节点$jj$结尾的回文串,每插入一个字符后将$cnt[i][last]cnt[i][last]$置为$11$表示有回文串结尾.

枚举每个字符串$jj$,令$pam\mathrm{.}cnt[j][pam\mathrm{.}fail[i]]\mathrm{\mid }=pam\mathrm{.}cnt[j][i]pam.cnt[j][pam.fail[i]]\backslash \; |=\backslash \; pam.cnt[j][i]$,类似于将$cnt[j][i]cnt[j][i]$累加到$cnt[j][pam\mathrm{.}fail[i]]cnt[j][pam.fail[i]]$上.对每个字符串,检查其Trie树上是否存在对应的节点,若所有字符串都存在该节点,即该节点表示的回文串是所有字符串的一个公共回文串,令$ans++ans++$即可.因每个节点表示的回文串是本质不同的,故不会有被重复统计的回文串.

代码

const int MAXN = 6e5 + 5;
int n;
char str[MAXN];
int tot;  // PAM总节点数
struct PAM {
	int siz;  // 当前用到的节点下标
	int root0, root1;  // 偶根、奇根
	int len[MAXN];  // len[u]表示节点u表示的回文串的长度
	int trie[MAXN][30];  // trie[u][ch]表示在节点u表示的回文串两边各添加一个字符ch得到的回文串对应的节点
	int fail[MAXN];  // fail[u]表示节点u的后缀边指向的节点
	int cnt[10][MAXN];  // cnt[i][j]表示第i个字符串是否有以节点j结尾的回文串
	int last;  // 指向最长回文串的结尾

	PAM() {
		siz = 0;
		root0 = siz++, last = root1 = siz++;
		len[root0] = 0, fail[root0] = root1;  // 偶根的fail指向奇根
		len[root1] = -1, fail[root1] = root1;
	}

	int get_fail(int u, int idx) {
		while (str[idx] != str[idx - len[u] - 1]) u = fail[u];  // 沿fail指针回跳到其最长回文后缀
		return u;
	}

	void insert(int i, char ch, int idx) {
		ch -= 'a';
		int u = get_fail(last, idx);
		while (!trie[u][ch]) {
			int cur = ++siz;  // 新建节点
			len[cur] = len[u] + 2;  // 子节点的len等于父节点的len+2
			int v = get_fail(fail[u], idx);
			fail[cur] = trie[v][ch];
			trie[u][ch] = cur;
		}
		last = trie[u][ch];
		cnt[i][last] = 1;  // 标记回文串结尾
	}
}pam;

void solve() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		pam.last = 0;
		cin >> str + 1;
		for (int j = 1; str[j]; j++) pam.insert(i, str[j], j);
	}

	int ans = 0;
	for (int i = pam.siz; i >= 1; i--) {
		for (int j = 0; j < n; j++) pam.cnt[j][pam.fail[i]] |= pam.cnt[j][i];

		int ok = 1;
		for (int j = 0; j < n; j++) ok &= pam.cnt[j][i];  // 检查所有串是否有相同的Trie节点
		ans += ok;
	}
	cout << ans;
}

int main() {
	solve();
}