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

使用 char* 指针比使用 String class 更容易，后者更像 Java 的方法。然后，您使用带有嵌套循环的相同算法结构并计算子字符串长度（从 first 到下一个大写字母 ），如果它比任何其他子字符串长，则使用 char* 或进行新分配如果必须使用 String class，则创建一个新的 String 对象。当然，你从最长的0值开始：

unsigned int longest_substring = 0;

如果找到更大的值，正如我已经说过的，您将其更改为它的长度并重新分配输出字符串 (char[]/char*) 变量。

为了让所有这些都起作用，你需要循环计数器，longest_string，current_string（用于在嵌套循环中检查的子字符串的长度），当然还有 char*/String to存储到目前为止最长的子字符串。

我很着急，所以无法提供代码，但这就是逻辑:-)

Answer 2

问题是l变量是子串的长度+1...注意j索引是一个超过子字符串的最后一个字符。

所以，要做到正确：

将 if 语句更改为：

   if(v.size()<=2) {l=max(l,j-i); if(l==j-i) index=i;}

Answer 3

如果您将调试输出添加到您的代码以查看它找到了哪些字符串：

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-th 字符：http://www.cplusplus.com/reference/string/string/string/ :

template <class InputIterator>
   string  (InputIterator first, InputIterator last);
Copies the sequence of characters in the range [first,last), in the same order.

请注意 last 不包括在内。

所以你的l应该是相应计算的：j-i，而不是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)的解决方案，只是需要更高级的代码。

Answer 4

算法没问题（当然是蛮力的，没什么花哨的）。然而，内部循环中生成的子字符串被误解了。

子串是从索引i到索引j-1（均包含在内），不包含索引j。因此，子字符串的长度必须为 (j-1 - i +1) = j-1 。必须使用此正确长度更新索引和长度变量。

这是错误的来源。顺便说一下，在可能的答案中，算法 returns 根据字符串中的位置最后一个子字符串。

Answer 5

也许最好重写你的代码：

#include <iostream>
#include <string>

using namespace std;

int main()
{
   string s = "AllPossibleSubstrings";
   int max=0,index=0;
   for(int i =0;i<s.length();i++)
   {
       int j=i;
       for(;s[j]==s[i];j++);
       if((j-i+1)>max)
       {
       max = (j-i+1);
       index = i;
       }
   }
   cout<<max<<" "+s.substr(index,max)<<endl;
}

编辑还应该再加一个check.The结果是循环体会变成这样：

   int j=i+1;
   for(;(s[j]==s[i] && j<n);j++);
   if(j==n) break;
   int z=j+1;
   for(;(s[z]==s[i]||s[z]==s[j]);z++);
   if((z-i)>max)
   {   
   max = (z-i);
   index = i;
   }

Answer 6

我修改了你的代码，如果我做对了答案是找到的任何一个，如果你希望你可以将它们存储在数组或其他东西中并显示所有相同的大小（最长的相同）。这是您可以获得的尽可能多的蛮力。

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

using namespace std;

int main(int args, char argv[]){
    string s = "AllPossibleSubstrings";
    string output = string();

    int starts_from = 0, length = 0;

    for (int i = 0; i < s.length(); i++){
            string sub = string();

            sub += s[i];

            int characters = 1;
            bool not_found = false;

            for (int j = i + 1; j < s.length() && characters <= 2; j++){
                for (int k = 0; k < sub.length(); k++)
                    if (s[j] != sub[k])
                        not_found = true;

                    if (not_found && characters == 1){
                        sub += s[j];
                        characters++;
                    }
                    else if (not_found && characters == 2)
                        break;
                    else
                        sub += s[j];
            }


            if (sub.length() > length){
                length = sub.length();
                starts_from = i; // index + 1 for the >1 value
                output = sub;
            }
    }

    cout << endl << "''" << output << "''" << " which starts from index " << starts_from << " and is " << output.length() << " characters long.." << endl;

    system("pause");

    return 0;
}

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

Longest substring with only 2 distinct chars in C++

c++

string

stl

set