C++中最长的非重复子串

Question

我正在尝试查找没有重复字符的最长子字符串。我有一个布尔向量来跟踪 256 个 ascii 字符。

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    string s = "aaaaaaaaaaaaasadfrhtytbgrbrsvsrhvsg";
    vector<bool> v(256, false);
    int j = 0, len = 0, index = 0;

    for(int i = 0; i < s.length(); i++)
    {
        if(!v[s[i]])
        {
            j++;

            if(j > len)
            { 
                len = j;
                index = i - j;
            }

            v[s[i]] = true;
        }
        else
        {
            j = 0;
            v.clear();
        }
    }

    cout << s.substr(index, len) + " " << len << endl;
}

我能理解为什么它给出输出 adfrht 6 ，而正确的输出是 sadfrhty 8.

Answer 1

您得到错误结果的原因是基本方法缺少一些移动部分。您没有跟踪计算此所需的所有信息。您不仅需要跟踪您看到了哪些字符，还需要跟踪它们在字符串中的哪个位置（我假设您希望将其保持在 O(n) 复杂度）。

这样，当您看到以前遇到过的字符时，您需要重置 "consecutive non-repeated characters seen so far" 计数器以在之前出现的相同字符之后开始你正在看，在当前位置。此外，到目前为止看到的所有字符，直到那个时候，都不再看到了，因为如果你想一想，它应该对你有意义。

这是您的实施中缺少的部分。另外，它没有跟踪最长字符串的位置，非常正确。

以下应该会产生您要查找的结果。

让我们知道您的家庭作业成绩:-)

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    string s = "aaaaaaaaaaaaasadfrhtytbgrbrsvsrhvsg";
    vector<bool> v(256,false);
    vector<int> seen_at(256);

    int longest_starting_pos=0, longest_length=0;

    int current_length=0;

    for (int i=0; i<s.length(); i++)
    {
        if (v[s[i]])
        {
            for (int j=i-current_length; j<seen_at[s[i]]; ++j)
                v[s[j]]=false;
            current_length=i-seen_at[s[i]]-1;
        }

        v[s[i]]=true;
        seen_at[s[i]]=i;
        if (++current_length > longest_length)
        {
            longest_length=current_length;
            longest_starting_pos=i-current_length+1;
        }
    }

    cout<<s.substr(longest_starting_pos, longest_length)+" "<<longest_length<<endl;
}

Answer 2

你的算法不正确。您的算法的问题在于，一旦它检查了一个字符，如果包含该字符的子字符串不是最长的，它就不会返回该字符再次检查它。第一个 s 正在检查长度为 2 的字符串 as，但是当找到下一个 a 时，忘记了 s，即使它可以使下一个子串更长。试试这个代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    string s = "aaaaaaaaaaaaasadfrhtytbgrbrsvsrhvsg";
    vector<bool> v(256,false);
    int longStart = 0;
    int longEnd = 0;
    int start = 0

    for (end = 0; end < s.length(); end++)
    {
        if (!v[s[end]])   // if character not already in the substring
        {
            v[s[end]] = true;

            if (end - start > longEnd - longStart)
            {
                longEnd = end;
                longStart = start;
            }
        }
        else   //the character is already in the substring, so increment the
               //start of the substring until that character is no longer in it
        {
            //get to the conflicting character, but don't get to the new character
            while ((s[start] != s[end]) && (start < end))
            {
                start++;
                v[s[start]] = false;
            }

            //remove the conflicting character
            start++;
            //don't set v[s[start]] to false because that character is still
            //encountered, but as the newly appended character, not the first
        }
    }

    longEnd++;    //make longEnd the index after the last character for substring purposes
    cout << s.substr(longStart, longEnd - longStart) + " " << (longEnd - longStart) << endl;
}

基本上这段代码所做的是保留一个运行子字符串，每当它遇到一个已经在子字符串中的字符时，它会递增子字符串的开头，直到新字符不再在子串，然后照常继续。如果该子字符串比以前认为最长的子字符串长，它还会在每次结尾递增时进行检查。这是 O(n) 我相信如你所愿。

此外，传播您的代码。如果您不能轻松阅读和调试代码，那么简洁的代码毫无意义。此外，如果您的代码有问题，请手动解决所有问题，以更好地了解它的工作原理和发生的情况。

希望对您有所帮助！

C++中最长的非重复子串

Longest Non Repeating Substring in c++

c++

algorithm

substring