C++中只有2个不同字符的最长子字符串

Question

我试图找到最长的子串,最多2个不同的字符.这是一个蛮力程序,只使用所有可能的子串并检查它们是否有2个或更多不同的字符.

我用一套来跟踪不同的字符.

#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_set>

using namespace std;

int main()
{
   string s = "AllPossibleSubstrings";
   int l=0,index=0;
   for(int i =0;i<s.length();i++)
   {
       for(int j=i+1;j<s.length();j++)
       {
           string sub = string(s.begin()+i,s.begin()+j);
           unordered_set<char> v;
           for(auto x:sub)
           {
               v.insert(x);
           }
           if(v.size()<=2) {l=max(l,j-i+1); if(l==j-i+1) index=i;}
       }
   }

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

}

我得到了错误的答案4 ssib,而正确的答案一定不能有b(All,llP,oss,ssi都是可能的答案).我哪里做错了？

Answer 1

如果将调试输出添加到代码中以查看它找到的字符串:

if(v.size()<=2) {
    l=max(l,j-i+1); 
    if(l==j-i+1) {
        index=i;
        cout << "Found match " << i << " " << j << " " << l << " " << sub << endl;
    }
}

你会发现它找到了正确的字符串:

Found match 0 1 2 A
Found match 0 2 3 Al
Found match 0 3 4 All
Found match 1 4 4 llP
Found match 4 7 4 oss
Found match 5 8 4 ssi

(见这里:http://ideone.com/lQqgnq)

但是,你也将看到,例如,对于i=5和j=8你sub="ssi",但是l=4,这显然是错误的.

因此,对错误行为的原因是,string(s.begin()+i,s.begin()+j)使子从起始i个字符和高达,但不包括中,j个字符:http://www.cplusplus.com/reference/string/string/string/:

template <class InputIterator>
   string  (InputIterator first, InputIterator last);

按相同顺序复制[first,last]范围内的字符序列.

请注意,last不包括在内.

所以你l应该相应地计算:as j-i,not j-i+1.

实际上,原因是您的代码过于复杂.您明确s.substr在代码的末尾使用,为什么不在主循环中使用相同的代码？你甚至可以有环绕在i和l,然后你就不会出现这样的问题.

而且,实际上每次都不需要提取子字符串.你可以循环i,l并保持当前不同的字符集.这将产生更快的O(N^2)解决方案,而你的解决方案O(N^3).就像是:

for (int i=0; i<s.length(); i++) {
   unordered_set<char> v; 
   for (int l=1; l<s.length()-i; l++) 
       v.insert(s[i+l-1]);
       if (v.size()>2) break;
       if (l>maxl) {
            index = i;
            maxl = l;
       }
}

实际上,即使是一个O(N)解决方案也可以在这里实现,但使用更高级的代码.