题解 | 子串计算

为什么我写之前的题这么卡

首先是脑子糊了不知道怎么枚举子串，其次是忘了忽略已经统计过的子串，还有就是自己只知道find一个参数的用法

// #include <iostream>
// #include <string>
// #include <map>
// #include <vector>
// #include <algorithm>
// using namespace std;

// // 统计所有子串的出现次数，返回类型是一个容器
// map<string, int> countSubstrings(const string &s) {
//     map<string, int> subCount;
//     int n = s.length();

//     // 遍历所有可能的子串，从i开始枚举n次，每次从i枚举到最后，外层循环i是开始位置，内层循环j是结束位置
//     for (int i = 0; i < n; ++i) {
//         string substring;
//         for (int j = i; j < n; ++j) {
//             substring += s[j]; // 每次累加当前字符逐步构建子串
//             subCount[substring]++; // 在map中记录该字串的出现次数
//         }
//     }

//     return subCount;
// }

// int main() {
//     string s;
//     // 循环输入
//     while (cin >> s) {
//         map<string, int> subCount = countSubstrings(s);

//         // map默认按键的字典序排序，但如果我们想按值（出现次数）排序，map无法直接支持
//         // 将结果存储到vector中以便排序，容器中每一个对象都是字符串与整型
//         vector<pair<string, int>> result;
//         // auto自动推导变量的类型，pair 是 map 中存储的键值对类型，即 pair<string, int>
//         for (const auto &pair : subCount) { // const表示只读，不能修改，避免后面的引用修改数据
//             if (pair.second > 1) { // pair.second表示该子串的出现次数，将出现次数在1次以上的子串存到vector中
//                 result.push_back(pair);
//             }
//         }

//         // 按字典序排序
//         sort(result.begin(), result.end());

//         // 输出结果
//         for (const auto &pair : result) {
//             cout << pair.first << " " << pair.second << endl;
//         }
//     }

//     return 0;
// }

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main() {
    string s;
    while (cin >> s) {
        map<string, int> count;

        // 外层i表示子串起点，内层一直从起点及以后遍历到末尾
        for (int i = 0; i < s.size(); i++) {
            string temp = "";
            for (int j = i; j < s.size(); j++) {
                temp += s[j];
                int pos = 0;
                // 允许重叠，若不允许重叠pos+=temp.size()
                // find两个参数，从pos处开始查找
                if (count.find(temp) == count.end()) {  // 如果之前已经统计过该字符串无需再统计
                    while ((pos = s.find(temp, pos)) != string::npos) {
                        count[temp]++;
                        pos++;
                    }
                }
            }
        }

        for (auto it = count.begin(); it != count.end(); it++) {
            if (it->second > 1) {
                cout << it->first << " " << it->second << endl;
            }
        }
    }
    return 0;
}