如何查找字符串中最长的连续子字符串？

例如，有它包括了1s和0s给定的字符串：如何查找字符串中最长的连续子字符串？

s = "00000000001111111111100001111111110000";

什么是有效的方式来获得最长1秒s中串的数量？（11）
什么是有效的方法来计算s中最长的0s子串的数量？（10）

我明白这个问题会从算法的角度来回答。

来源

2012-11-21 Think Recursively

你可以在这个前面的线程中找到你的答案http://stackoverflow.com/questions/3458726/find-out-how-long-the-longest - 序列是字符串 –

作业？尝试过什么？ –

不是作业，这是我的项目中提出的一个问题。我可以使用多个标志来解决这个问题，例如：int one_start; int one_end; int one_count; int max_one_count; int zero_start; int zero_end; int zero_count; int max_zero_count;但我想知道是否有更好的方法来解决它。 –

我认为最直接的方法是在记录所有0和所有1子字符串的最大长度的同时遍历位串。正如其他人所建议的那样，它的复杂性为O (n)。

如果你能买得起某种数据并行计算，你可能想看看here解释的并行模式。具体来说，看看parallel reduction。我认为这个问题可以在O (log n)时间内实施，如果你能负担得起这些方法之一。

我试图想一个平行减少对这个问题的：

在减速装置的第一级，每个线程会处理8位串的数据块（取决于线程数你有与字符串的长度）和产生的比特串等的摘要：0 -> x, 1 -> y, 0 -> z, ....
在下一级别的每个线程将合并两个这些摘要成一个，任何可能加入将在该阶段中进行（基本上，如果以前的总结结束了使用0（1）编辑并且下一个摘要以0（1）开始，然后可以将最后的条目和两个摘要的第一个条目合并为一个）。
在顶层将只有一个结构，包含位串的总体概要，您必须逐步了解最大序列（但这次它们都是汇总形式，所以它应该更快）。或者，您可以使每个摘要结构跟踪大字符0和1子字符串，这将使得不需要遍历最终结构。

我想这种做法才有意义，在非常有限的范围内，但因为你似乎是在获得比O (n)更好十分热衷......

来源

2012-11-21 11:53:14

感谢您的评论，您能否详细说明代码的简单方法？ –

@QSortBSearch：这是非常微不足道的，[这里是]（http://tny.cz/f06863ca/fulldot.php?hash=4bdd71c81291f1d54f66d06ae15cea83&toolbar=true&linenum=false）递归实现。不想让这个代码混淆回答。 –

OK，这里是一个解决方案，我想出了，我不确定这是否没有缺陷。纠正我，如果你发现一个错误或建议更好的方法来做到这一点。如果您同意此解决方案，请投票。谢谢！

#include <iostream> 

using namespace std; 

int main(){ 

    int s[] = {0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0}; 
    int length = sizeof(s)/sizeof(s[0]); 

    int one_start = 0; 
    int one_n = 0; 
    int max_one_n = 0; 

    int zero_start = 0; 
    int zero_n = 0; 
    int max_zero_n = 0; 

    for(int i=0; i<length; i++){ 
     // Calculate 1s 
     if(one_start==0 && s[i]==1){ 
      one_start = 1; 
      one_n++; 
     } 
     else if(one_start==1 && s[i]==1){ 
      one_n++; 
     } 
     else if(one_start==1 && s[i]==0){ 
      one_start = 0; 
      if(one_n > max_one_n){ 
       max_one_n = one_n; 
      } 
      one_n = 0;  // Reset 
     } 

     // Calculate 0s 
     if(zero_start==0 && s[i]==0){ 
      zero_start = 1; 
      zero_n++; 
     } 
     else if(zero_start==1 && s[i]==0){ 
      zero_n++; 
     } 
     else if(one_start==1 && s[i]==1){ 
      zero_start = 0; 
      if(zero_n > max_zero_n){ 
       max_zero_n = zero_n; 
      } 
      zero_n = 0;  // Reset 
     } 
    } 

    if(one_n > max_one_n){ 
     max_one_n = one_n; 
    } 
    if(zero_n > max_zero_n){ 
     max_zero_n = zero_n; 
    } 

    cout << "max_one_n: " << max_one_n << endl; 
    cout << "max_zero_n: " << max_zero_n << endl; 

    return 0; 
}

来源

2012-11-21 17:18:20

最坏的情况总是O（n），你总是可以找到强制算法检查每一位的输入。

但是，你可能平均略胜一筹（更简单地说，如果你只扫描0或1，而不是两者），因为你可以跳过当前找到的最长序列的长度并向后扫描。至少这会减少O（n）的常数因子，但至少在随机输入的情况下，更多的项目也意味着更长的序列，并且因此更长和更长的跳跃。但与O（n）的差别不会太大......

来源

2012-11-21 18:14:11 hyde

如何查找字符串中最长的连续子字符串？

回答

相关问题