SDUT 3308 最长01串

最长01串

Time Limit: 2666 ms; Memory Limit: 65536 KiB

Problem Description

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

Input

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

Output

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

Sample Input

1011
1111
1010

Sample Output

2
0
4

题目链接：http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3308.html

题目分析：记录0和1个数差出现的位置

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const CON = 1000000;
char s[1000005];
int mp[2000005];

int main() {
    while (scanf("%s", s) != EOF) {
        int diff = 0, ans = 0;
        memset(mp, -1, sizeof(mp));
        for (int i = 0; i < strlen(s); i++) {
            diff += (s[i] == '1');
            if (diff == 0) {
                ans = max(ans, i + 1);
            } else {
                if (mp[diff + CON] == -1) {
                    mp[diff + CON] = i;
                } else {
                    ans = max(ans, i - mp[diff + CON]);
                }
            }
        }
        printf("%d\n", ans);
    }
}