【2016 BUAA ACM选拔赛 zxa and UAV】Trie | BFS/DFS | E

【2016 BUAA ACM选拔赛】 zxa and UAV

时间限制: 2000 ms 内存限制: 131072 kb 总通过人数: 12 总提交人数: 15

Tags：BFS/DFS Trie

题目描述

多组数据。每组给定两个各含 n n n 个字符串的字符串集合（全为小写字母组成的字符串）。

要把两个集合中的串两两配对，并将每一对的最长公共前缀长度相加，称其为总相似度。

求总相似度的最大值。

输入

多组（组数 ≤ 10 \le 10 ≤10）。以 EOF 结尾。

对于每组数据，包含若干行，第一行一个正整数 n n n，代表每个集合包含的串个数。

接下来 n n n 行每行一个字符串，表示第一个集合。

接下来 n n n 行每行一个字符串，表示第二个集合。

范围： 1 ≤ n ≤ 50000 1≤n≤50000 1≤n≤50000，并且每组数据字符串总长 ≤ 1 0 6 \le 10^6 ≤106。保证字符串皆仅由小写字母组成。

输出

每组输入对应输出一行一个非负整数，即总相似度的最大值。

输入样例

5
gennady
galya
boris
bill
toshik
bilbo
torin
gendalf
smaug
galadriel

           

输出样例

11

           

分析

找 “最多公共前缀” ：

不妨考虑利用 Trie 来表示字符串集合，然后找最多公共前缀就等价于找这两棵树的、以各自根结点为根的最大公共子树。

何为 “最大” ？应是每个结点的 度 之和最大。

因此在两棵树上同步跑 BFS/DFS 找出他们的最大公共子树，并顺便计数即可。

（另外注意不要超内存）

时间复杂度：

• 建树和同步搜索（DFS or BFS）都是 O ( ∑ i = 1 n l e n i ) O(\sum\limits_{i=1}^{n} len_i) O(i=1∑n​leni​) 的。
• 总时间复杂度也是 O ( ∑ i = 1 n l e n i ) O(\sum\limits_{i=1}^{n} len_i) O(i=1∑n​leni​) 的 。

AC代码

#include <cstdio>
#include <cstring>

constexpr int MN(6e5+6);
constexpr int ML(1e6+6);
constexpr int MA(26);

#define MIN(a, b) ((a)<(b)?(a):(b))
#define IDX(c) ((c)-'a')

class Trie
{
//private:
public:

	struct Node
	{
		int next[MA];
		int cnt;
	} t[MN];

	int tot;
	const int ROOT = 0;

public:

	inline void clear(void)
	{
		tot = 0;
		memset(t, 0, sizeof(t));
	}

	void insert(const char *p)
	{
		int now = ROOT;
		for (; *p; ++p)
		{
			if (!t[now].next[IDX(*p)])
				t[now].next[IDX(*p)] = ++tot;
			++t[now = t[now].next[IDX(*p)]].cnt;
		}
	}

	inline const Node & operator [](const int x) const
	{
		return t[x];
	}
} T1, T2;


int ans;
char s[ML];
int q1[MN], q2[MN];

int bfs(void)
{
	int cnt = 0;
	int h1 = 0, t1 = 0, h2 = 0, t2 = 0;
	q1[t1++] = T1.ROOT, q2[t2++] = T2.ROOT;
	while (h1 != t1)
	{
		const int u1 = q1[h1++], u2 = q2[h2++];
		cnt += MIN(T1[u1].cnt, T2[u2].cnt);
		for (int i=0; i<MA; ++i)
		{
			const int v1 = T1[u1].next[i], v2 = T2[u2].next[i];
			if (v1 && v2)
			{
				q1[t1++] = v1, q2[t2++] = v2;
			}
		}
	}
	
	return cnt;
}


int main()
{
	int n;
	while (~scanf("%d", &n))
	{
		ans = 0;
		T1.clear();
		T2.clear();

		for (int i=0; i<n; ++i)
		{
			scanf("%s", s);
			T1.insert(s);
		}
		for (int i=0; i<n; ++i)
		{
			scanf("%s", s);
			T2.insert(s);
		}

		printf("%d\n", bfs());
	}

	return 0;
}
           

BCPC + 2019选拔赛要来了，加油鸭！