---
title: "查询字符串"
created: 2025-11-28
tags:
  - 算法
---

# 查询字符串

## 题目 [查询字符串](https://www.acwing.com/problem/content/description/4401/)

![[image-1c99f7e3.png]]

## 思路分析

数据中每个字符串最长为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**

```cpp
#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;

}

//会发现异常的麻烦
```

**哈希**

```cpp
//其实可以直接枚举每个子串 以子串为键 存在哈希表里面

//逻辑基本一样 意思是说 转换成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;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[字典树|字典树]] 🏠 [[00-刷题理模型]] ➡️ [[电话列表|电话列表]]