时间戳

首页 > 解决方案 > 是否有用于查找字符串中最长且不重复长度的子字符串的结构函数？

c++ - 是否有用于查找字符串中最长且不重复长度的子字符串的结构函数？

问题描述

该函数的目的是找出最长且不重复的子字符串，因此我需要找出子字符串的起始位置及其长度。我正在努力解决的问题是大 O 符号应该是 O(n)。因此我不能使用嵌套的 for 循环来检查每个字母是否重复。我创建了一个这样的结构函数，但我不知道如何继续：

struct Answer {             
    int start;              
    int length;
};

Answer findsubstring(char *string){
    Answer sub={0, 0}

    for (int i = 0; i < strlen(string); i++) {
        
    }
    return (sub)
}

比如输入是HelloWorld，输出应该是World。长度是5。如果输入是abagkfleoKi，那么输出是bagkfleoKi。长度为 10。另外，如果两个字符串的长度相同，则选择后一个。

标签： c++

解决方案

使用 astd::unordered_map<char, size_t>将索引存储在某个字符的最后一次出现之后。

保留当前最佳匹配以及您当前测试的匹配。在需要处理的 2 种情况下遍历输入结果的字符：

  1. char 已经出现并且 char 的最后一次出现要求您移动潜在匹配的开始以避免 char 出现两次：如果这比当前的答案更好，则使用在当前 char 之前结束的匹配更新答案。
  2. 否则：只需更新地图
void printsubstring(const char* input)
{
    std::unordered_map<char, size_t> lastOccurances;

    Answer answer{ 0, 0 };

    size_t currentPos = 0;
    size_t currentStringStart = 0;

    char c;

    while ((c = input[currentPos]) != 0)
    {
        auto entry = lastOccurances.insert({ c, currentPos + 1 });

        if (!entry.second)
        {
            if (currentStringStart < entry.first->second && currentPos - currentStringStart > answer.length)
            {
                // need to move the start of the potential answer
                // -> check, if the match up to the char before the current char was better
                answer.start = currentStringStart;
                answer.length = currentPos - currentStringStart;
                currentStringStart = entry.first->second;
            }
            
            entry.first->second = currentPos + 1;
        }
        ++currentPos;
    }

    // check the match ending at the end of the string
    if (currentPos - currentStringStart > answer.length)
    {
        answer.start = currentStringStart;
        answer.length = currentPos - currentStringStart;
    }

    std::cout << answer.start << ", " << answer.length << std::endl;
    std::cout << std::string_view(input + answer.start, answer.length) << std::endl;
}

推荐阅读