时间戳

首页 > 解决方案 > 返回子字符串

c++ - 返回子字符串

问题描述

我如何将它用于 x 数量的数字？对于我的方法，它硬编码为 2 个子字符串。还有时间复杂度更低的更好方法吗？这里可能有一个漏洞，需要修正 num im 传递的数量，因为我根本没有使用 um 参数。

标签： c++

解决方案

您当前的方法存在一些问题，包括硬编码的最大 ngram 数和固定的 ngram 大小。此外，您的短变量名和缺少注释无助于向正在阅读代码的人解释代码。

一个更简单的解决方案是使用 amap来计算每个 ngram 出现的次数，然后找到计数最高的那个。这将带来大约N.logN时间复杂度。或者unordered_map将更接近线性时间复杂度。

当然会有一个极端情况，即多个 ngram 出现相同的最高计数。您需要决定应使用多种策略中的哪一种来解决该问题。在我的示例中，我利用内部排序std::map来选择排序顺序最低的 ngram。如果使用unordered_map，您需要一种不同的策略来确定性地解决争用。

#include <algorithm>
#include <iostream>
#include <map>
#include <string>

std::string ngram(const std::string &input, int num)
{
    if (num <= 0 || num > input.size()) return "";

    // Count ngrams of size 'num'
    std::map<std::string, int> ngram_count;
    for(size_t i = 0; i <= input.size() - num; i++)
    {
        ++ngram_count[input.substr(i, num)];
    }

    // Select ngram with highest count
    std::map<std::string, int>::iterator highest = std::max_element(
        ngram_count.begin(), ngram_count.end(),
        [](const std::pair<std::string, int>& a, const std::pair<std::string, int>& b)
        {
            return a.second < b.second;
        });

    // Return ngram with highest count, otherwise empty string
    return highest != ngram_count.end() ? highest->first : "";
}

int main()
{
    std::cout << ngram("engineering", 2) << std::endl;
    std::cout << ngram("engineering", 3) << std::endl;
    return 0;
}

推荐阅读