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

Question

我试图找到没有重复字符的最长子串。我有一个 bool vector 来跟踪 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) 复杂度)。

这样，当您看到以前遇到过的字符时，您需要将“到目前为止看到的连续非重复字符”计数器重置为 在上次出现的相同字符之后开始你正在看，在当前位置。此外，到目前为止看到的所有字符，直到那时，都不再看到了，因为如果你想一想，它应该对你有意义。

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

以下应该会产生您正在寻找的结果。

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

#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;
}