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，whreas正确的输出是sadfrhty 8

Answer 1

为什么你会得到错误结果的原因是因为基本的方法是缺少了几件移动。您没有跟踪所有需要计算的信息。不仅需要跟踪你所看到的字符，还需要跟踪字符串中的哪个位置（我认为你希望保持这种复杂度）。

这样，当你看到一个已经遇到过一个角色，你需要重置计数器后开始相同字符的上一个出现，你要找的“见过这么远的连续非重复的字符”在，在当前位置。此外，到目前为止，迄今为止看到的所有角色都不再被看到，因为如果你想一秒钟，它应该对你有意义。

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

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

让我们知道您的家庭作业收到什么档次:-)

#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）我相信你想要的。

此外，传播你的代码。简明的代码意味着什么，如果你不能读取和调试它很容易。此外，如果您的代码存在问题，请全部手动完成，以便更好地了解它的工作原理和发生的情况。

希望这会有所帮助！