最长01串

浅浅的花香味﹌ 2022-08-18 02:30 185阅读 0赞

## 最长01串 ##

####  ####

##### Time Limit: 2666ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

给定一个0-1串，请找到一个尽可能长的连续子串，其中包含的0与1的个数相等。  
组数很多，注意常数优化。。。

## 输入 ##

一个字符串，只包含 01 ，长度不超过 1000000

## 输出 ##

一行一个整数，最长的 0 与 1 的个数相等的子串的长度。

## 示例输入 ##

1011
    1111
    1010

## 示例输出 ##

2
    0
    4

## 提示 ##

## 来源 ##

scf0920

## 示例程序 ##

#include<iostream>  
    #include<cstdio>  
    #include<cstring>  
    #include<cstdlib>  
    #include<algorithm>  
    #include<map>  
      
    using namespace std;  
      
    int a[1000][1000];  
    int vis[2000010];  
    char s[1000010];  
    int main()  
    {  
        while(~scanf("%s",s))  
        {  
            int len=strlen(s);  
            int sum=0,Max=0;  
            memset(vis,-1,sizeof(vis));  
            for(int i=0; i<len; ++i)  
            {  
                if(s[i]=='1')  
                    sum++;  
                if(s[i]=='0')  
                    sum--;  
                if(sum==0)  
                {  
                    Max=max(Max,i+1);  
                        continue;  
                }  
                if(vis[1000000+sum]==-1)    
                    vis[1000000+sum]=i;  
                else                                                   
                {  
                    Max=max(i-vis[1000000+sum],Max);   
                }  
            }  
            printf("%d\n",Max);  
        }  
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，185人围观）

还没有评论，来说两句吧...

相关阅读

相关最长公共子串

题目： [\[编程题\]最长公共子串][Link 1] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_

男娘i/ 2022年12月07日 15:23/ 0 赞/ 182 阅读

相关最长公共子串

/ 求最长公共子串 / public class Solution8 { public static void main(String[]

阳光穿透心脏的1/2处/ 2022年10月29日 11:17/ 0 赞/ 170 阅读

相关最长公共子串

[lintcode练习题目][lintcode] include "string" include "stdio.h" include "iostre

ゝ一世哀愁。/ 2022年09月24日 12:23/ 0 赞/ 192 阅读

相关最长01串

最长01串 Time Limit: 2666ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述给定一个0-1串，请找到

浅浅的花香味﹌/ 2022年08月18日 02:30/ 0 赞/ 186 阅读

相关最长公共子串与最长连续子串算法

利用DP思想最长公共子串中result\[i\]\[j\]存放str1前i个与result\[j\]个的最长公共子串，当str1\[i + 1\]==str2\[j + 1

男娘i/ 2022年08月11日 16:44/ 0 赞/ 221 阅读

相关最长01子串

【题目】给定一个数组，数组中只包含0和1。请找到一个最长的子序列，其中0和1的数量是相同的。例1：10101010 结果就是其本身。例2：1101000

电玩女神/ 2022年07月29日 11:56/ 0 赞/ 177 阅读

相关最长对称子串

最长对称子串：给出一个字符串，求出它的最长的对称的子串的长度 \include<iostream> \include<cstdio> \include<algorit

秒速五厘米/ 2022年06月17日 13:59/ 0 赞/ 187 阅读

相关最长重复子串

思路：使用后缀数组解决分析： 1、由于要求最长公共子序列，则需要找到字符串的所有子串，即通过产生字符串的后缀数组实现。 2、由于要求最长的重复子串，则需要对所有子串进行

刺骨的言语ヽ痛彻心扉/ 2022年06月17日 03:16/ 0 赞/ 211 阅读

相关最长回文串

public String longestPalindrome(String s) { int start = 0, end = 0;

刺骨的言语ヽ痛彻心扉/ 2022年06月10日 10:22/ 0 赞/ 182 阅读

相关最长公共子串

最长公共子串（注意子串是连续的，也是与最长公共子序列的区别） 1、先建立一个二维数组array\[str1.size()\]\[str2.size()\]（全部初始化为0

秒速五厘米/ 2021年10月19日 05:48/ 0 赞/ 369 阅读