查询字符串
题目 查询字符串
思路分析
数据中每个字符串最长为8，把每个字符串出现的子串求出来就行了，最后查询输出即可
这就可以用trie树或者哈希表来做
trie树：
对于每个字符串 f，将 f 的所有以 f 的最后一个字符结尾的子串加入字典树
如：f = “.text”
则将 “.text”,”text”,”ext”,”xt”,”t” 都加入字典树 字典树的每个节点有一个指向字符串的指针集合 origin，记录其对应的字符串
对于每个查询，包含它的字符串的数量就是其对应的字典树节点中 origin 的大小，origin 中的任意一个字符串都可以作为答案。
哈希：
直接以string为键
枚举每一个字符串里的每一个子串（j枚举每个子串的开头位置，k枚举每个子串的结尾位置，再从j循环到k，把中间的一段字符存到另一个字符串t里）
如果这个子串在此字符串里没有出现，那么将(map)cnt[t]++(此子串出现次数+1)，并且将包含此子串的这个字符串存储到(map)ans[t]里
需要注意的是在处理每个字符串出现的子串的时候，出现多次子串但是最终计数只+1 因为输出的是出现子串的母串个数
显然发现一个问题 这种并非直接问前缀匹配的问题 想用trie是要比哈希要麻烦的
代码实现
trie
#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 37; // 26个字母 + 10个数字 + 1个点
const int MAX_NODE = 1e6;
int son[MAX_NODE][MAX_CHAR], idx;
unordered_map<string, set<string>> substrings; // 存储子串及其对应的原始字符串集合
// 将字符映射到0-36的索引
int charToIndex(char c) {
if (isdigit(c)) return 26 + (c - '0'); // 数字映射到26-35
if (c == '.') return 36; // 点映射到36
return c - 'a'; // 字母映射到0-25
}
// 将字符串的所有子串插入Trie树，并记录原始字符串
void insert(const string& s, const string& original) {
for (size_t length = 1; length <= s.size(); ++length) {
for (size_t start = 0; start + length <= s.size(); ++start) {
string sub = s.substr(start, length);
int p = 0; // 从根节点开始
for (char ch : sub) {
int u = charToIndex(ch);
if (!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
substrings[sub].insert(original);// 将原始字符串添加到子串对应的集合中
}
}
}
// 检查Trie树中是否存在包含特定子串的路径
bool query(const string& s) {
int p = 0;
for (char ch : s) {
int u = charToIndex(ch);
if (!son[p][u])
return false; // 如果在某个点上没有找到对应的子节点，说明不存在这样的子串
p = son[p][u];
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n;
string str;
for (int i = 0; i < n; ++i) {
cin >> str;
insert(str, str);
}
cin >> q;
for (int i = 0; i < q; ++i)
{
cin >> str;
// 检查子串是否存在于Trie树中
if (!query(str) || substrings.find(str) == substrings.end())
cout << "0 -\n";
else
// 输出包含子串的字符串数量和一个示例字符串
cout << substrings[str].size() << " " << *substrings[str].begin() << endl;
}
return 0;
}
//会发现异常的麻烦
哈希
//其实可以直接枚举每个子串 以子串为键 存在哈希表里面
//逻辑基本一样 意思是说 转换成trie那步完全是多余的
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n,q;
unordered_map<string,int> cnt;// 存储每个子串出现的次数
unordered_map<string,string> apper;// 存储每个子串对应的原始字符串
// 处理输入的字符串，计算所有可能的子串，并更新它们的出现次数及对应的原始字符串
void deal(string str) {
int length = str.size();
unordered_map<string, int> um; // 用于确保一个字符串中的子串只被计数一次
for (int len = 1; len <= length; len++)
{
int i = 0;
while (i + len - 1 < length)
{
string tmp = str.substr(i, len);
if (um[tmp] == 0) { // 如果该子串在当前字符串中尚未被计数
cnt[tmp]++; // 子串出现次数加一
um[tmp] = 1; // 标记该子串已被计数
apper[tmp] = str; // 记录该子串对应的一个原始字符串
}
i++;
}
}
}
int main() {
cin >> n;
string str;
for (int i = 0; i < n; i++) {
cin >> str;
deal(str); // 处理每个字符串，计算其所有可能产生的子串
}
cin >> q;
while (q--) {
cin >> str;
cout << cnt[str] << " "; // 输出该子串出现的总次数
if (cnt[str] == 0)
cout << "-" << "\n"; // 如果次数为0，输出"-"
else
cout << apper[str] << "\n"; // 否则，输出该子串对应的一个原始字符串
}
return 0;
}
💬 评论