思路

我们可以直接利用 Trie 树来贪心，树上每一个点都可以对答案产生 \(x\) 的贡献（\(x\) 为多少个这样的节点），而是否产生取决于 \(T\) 字符串是否可以到达这个节点，所以贪心来做，每搜到一个节点就判断 \(x\) 是否大于 \(0\)，即还能不能产生贡献，若能则 \(ans+1\)，再把当前节点的 \(x-1\)，不能就继续搜下去。注意，一旦在树上失配就 return，以保证前面产生贡献的点全满足前缀。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=3072005;
string name[N];
struct Node {
	bool word;
	int ch[30],num;
	Node() {
		word=0,memset(ch,0,sizeof(ch));
	}
};
Node trie[M];
int cnt=0;
void insert(string s) {
	int now=0;
	for(int i=0; i<s.size(); i++) {
		int tmp=s[i]-‘a‘;
		if(!trie[now].ch[tmp]) {
			trie[now].ch[tmp]=++cnt;
		}
		now=trie[now].ch[tmp];
		trie[now].num++;
	}
	trie[now].word=1;
}
int ans;
void find(string s) {
	int now=0;
	for(int i=0; i<s.size(); i++) {
		int tmp=s[i]-‘a‘;
		if(!trie[now].ch[tmp]) {
			return ;
		}
		now=trie[now].ch[tmp];
		if(trie[now].num) {
			ans++,trie[now].num--;
		}
	}
	return ;
}
int main() {
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
		string s;
		cin>>s,insert(s);
	}
	for(int i=1; i<=n; i++) {
		string s;
		cin>>s,find(s);
//		printf("%d\n",ans);//Debug
	}
	printf("%d",ans);
	return 0;
}

注意事项

跳转时注意所指的结点是否为所想的。

参考资料

T2 选ID trie树。

【GOJ 1864】选ID

原文：https://www.cnblogs.com/Sam2007/p/14731604.html