Chuỗi con dài nhất không lặp lại trong C++

Question

Tôi đang cố tìm chuỗi con dài nhất không có ký tự lặp lại. Tôi có một vectơ boolean để theo dõi 256 ký tự 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; 
} 

tôi có thể hiểu tại sao nó mang lại cho sản lượng adfrht 6, whreas đầu ra đúng là sadfrhty 8.

Answer 1

Lý do tại sao bạn đang nhận được kết quả sai là do cách tiếp cận cơ bản là thiếu một vài mẩu di chuyển . Bạn không theo dõi tất cả thông tin mà bạn cần để tính toán điều này. Không chỉ bạn cần phải theo dõi những nhân vật bạn đã thấy, mà còn ở vị trí nào trong chuỗi mà chúng được nhìn thấy (tôi đoán rằng bạn muốn giữ điều này ở độ phức tạp O (n)).

Bằng cách này, khi bạn nhìn thấy một nhân vật đã gặp phải trước đó, bạn cần phải đặt lại "các ký tự không lặp lại liên tiếp được thấy cho đến giờ" để bắt đầu sau lần xuất hiện trước đó của cùng một ký tự mà bạn đang tìm kiếm tại, ở vị trí hiện tại. Ngoài ra, tất cả các nhân vật đã được nhìn thấy cho đến nay, cho đến thời điểm đó, không còn nhìn thấy, bởi vì nếu bạn nghĩ về nó trong một giây, nó sẽ có ý nghĩa với bạn.

Đó là phần còn thiếu trong quá trình triển khai của bạn. Ngoài ra, nó không theo dõi vị trí của chuỗi dài nhất, khá đúng.

Sau đây sẽ tạo ra kết quả bạn đang tìm kiếm.

Cho chúng tôi biết những gì lớp bạn nhận được cho bài tập về nhà của bạ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; 
} 

Answer 2

thuật toán của bạn là không chính xác. Điều gì là sai với thuật toán của bạn là một khi nó kiểm tra một nhân vật, nó không quay trở lại nhân vật đó để kiểm tra nó một lần nữa nếu chuỗi con bao gồm ký tự đó không phải là dài nhất. Đầu tiên s đang được kiểm tra trong chuỗi có độ dài 2 là as, nhưng khi tìm thấy a tiếp theo, thì s bị lãng quên, mặc dù nó có thể làm cho chuỗi con tiếp theo dài hơn. Hãy thử mã này:

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

Về cơ bản những gì mã này không là nó giữ một chuỗi con chạy, và bất cứ khi nào nó gặp một nhân vật đã nằm trong chuỗi con, nó increments sự bắt đầu của chuỗi con cho đến khi nhân vật mới không còn trong chuỗi con, sau đó tiếp tục như bình thường. Nó cũng kiểm tra mỗi khi kết thúc được tăng lên nếu chuỗi con đó dài hơn chuỗi con dài nhất được tin trước đó. Đây là O (n) tôi tin như bạn muốn.

Ngoài ra, hãy truyền mã của bạn ra. Mã ngắn gọn có nghĩa là không có gì nếu bạn không thể đọc nó và gỡ lỗi một cách dễ dàng. Ngoài ra, nếu bạn gặp vấn đề với mã của mình, hãy làm việc tất cả bằng tay để hiểu rõ hơn về cách hoạt động của nó và những gì đang xảy ra.

Hy vọng điều này sẽ hữu ích!