洛谷【P4470】[BJWC2018]售票

最新推荐文章于 2025-06-02 20:51:47 发布

SP FA

最新推荐文章于 2025-06-02 20:51:47 发布

阅读量374

点赞数

分类专栏：习题文章标签：字符串算法 c++

本文链接：https://blog.csdn.net/SP_FA/article/details/104084797

版权

习题专栏收录该内容

10 篇文章

订阅专栏

本文介绍了一种使用字典树（Trie）进行字符串匹配的方法。通过建立字典树，文章展示了如何插入和搜索字符串，特别关注了数据范围和变量大小的考虑，以避免内存溢出。代码示例使用C++实现，详细解释了插入和搜索操作。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目链接
这道题其实很简单，数据范围也不大，直接暴力 DFS 就可以了。但是我想试一试字典树。

但是要注意的是，由于每个字符串可以到达 100 个字符，最多共有50个字符串，所以变量 tot 和 u 最坏可以到达 50*100 = 5000 ，所以 trie 数组的第一维要开大一些。

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
#define ASC s[i]-'A'

int n,tot;
int trie[10005][26],num[105];
char s[105],a[26]={     'A','B','C','D','E',
			'F','G','H','I','J','K','L','M',
			'N','O','P','Q','R','S','T','U',
			'V','W','X','Y','Z'};

void insert(void){
	int u=0;
	for(int i=0;s[i];i++){
		if(!trie[u][ASC])
			trie[u][ASC] = ++tot;
		u = trie[u][ASC];
	}
	return;
}
void search(void){
	int u=0;
	for(int i=0;s[i];i++){
		if(!trie[u][ASC]) return;
		u = trie[u][ASC];
	}
	for(int i=0;i<=25;i++)
		if(trie[u][i]) num[i]++;
}
int main(void){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> s;
		insert();
		memset(s,0,sizeof(s));
	}
	cin >> s;
	search();
	cout << "***";
	for(int i=0;i<=25;i++){
		if(!num[i]) cout << '*';
		else cout << a[i];
		if(i==4 || i==12 || i==20) cout << endl;
	}
	cout << "***" << endl;
	return 0;
}