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

此外，傳播你的代碼。簡明的代碼意味着什麼，如果你不能讀取和調試它很容易。此外，如果您的代碼存在問題，請全部手動完成，以便更好地瞭解它的工作原理和發生的情況。

希望這會有所幫助！