厦门响应式网站,做网站如何自己寻找客户,ps切片工具做网站,学校网站改版题目链接#xff1a;用户登录
题目#xff1a;
样例#xff1a; 输入 5 3
aaa
aba
aabbaa
abbbbb
cdd
aabba
abc
abab 输出 Y
N
N 思路#xff1a; 根据题目意思#xff0c;要用到 Trie 字典树算法。
Trie 字典树#xff0c;顾名思义#xff0c;“字典”#xff0…题目链接用户登录
题目
样例
输入 5 3
aaa
aba
aabbaa
abbbbb
cdd
aabba
abc
abab
输出 Y
N
N 思路 根据题目意思要用到 Trie 字典树算法。
Trie 字典树顾名思义“字典”我们查字典的时候都是找开头的几个字符来获取我们的整个字符Trie 字典树就是通过 前缀字符的一步步扩展。最后查找的时候就是根据我们扩展字典树的步骤来变相查找。字典树我们也要建立一个 root 跟
比如 给出以下的几个字符
abcdf
bgre
abfr
baef
最后获得的字典树为 下面给出 Trie 字典树封装的结构体 // 定义 Tries 结构体封装
struct Tries
{// son 用于存储 字符idx 对应映射整数地址int son[N][26],idx;// 构造 Tries 初始化inline Tries(){memset(son,0,sizeof son);idx 0;}// 字符串 插入操作inline void Insert(string str){int p 0; // 对应root根树的 映射地址int len str.size(); // 计算 字符串 的长度方便遍历for(int i 0;i len;i){int u str[i] - a; // 将 单个字符 转化为 映射整数地址if(!son[p][u]) son[p][u] idx; // 如果没有当前 地址扩展映射p son[p][u]; // 往 存在的结点地址 开始下一次检索}return ;}// 字符串 查找操作 和 插入操作相似只是不会新建结点inline bool query(string str){int p 0; // 对应root根树的 映射地址int len str.size(); // 计算 字符串 的长度方便遍历for(int i 0;i len;i){int u str[i] - a; // 将 单个字符 转化为 映射整数地址if(!son[p][u]) return false; // 如果没有当前 地址扩展映射p son[p][u]; // 往 存在的结点地址 开始下一次检索}return true;}
}tree;
代码详解如下
#include iostream
#include vector
#include queue
#include cstring
#include algorithm
#include unordered_map
#define endl \n
#define int long long
#define YES puts(YES)
#define NO puts(NO)
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,Ofast,inline)
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N 2e6 10;// 定义 Tries 结构体封装
struct Tries
{// son 用于存储 字符idx 对应映射整数地址int son[N][26],idx;// 构造 Tries 初始化inline Tries(){memset(son,0,sizeof son);idx 0;}// 字符串 插入操作inline void Insert(string str){int p 0; // 对应root根树的 映射地址int len str.size(); // 计算 字符串 的长度方便遍历for(int i 0;i len;i){int u str[i] - a; // 将 单个字符 转化为 映射整数地址if(!son[p][u]) son[p][u] idx; // 如果没有当前 地址扩展映射p son[p][u]; // 往 存在的结点地址 开始下一次检索}return ;}// 字符串 查找操作 和 插入操作相似只是不会新建结点inline bool query(string str){int p 0; // 对应root根树的 映射地址int len str.size(); // 计算 字符串 的长度方便遍历for(int i 0;i len;i){int u str[i] - a; // 将 单个字符 转化为 映射整数地址if(!son[p][u]) return false; // 如果没有当前 地址扩展映射p son[p][u]; // 往 存在的结点地址 开始下一次检索}return true;}
}tree;
int n,k;
string s;
inline void solve()
{cin n k;while(n--){cin s;tree.Insert(s);}while(k--){cin s;if(tree.query(s)) cout Y endl;else cout N endl;}
}signed main()
{
// freopen(a.txt, r, stdin);IOS;int _t 1;
// cin _t;while (_t--){solve();}return 0;
}
最后提交
