题目大意

给定一个0-1串，请找到一个尽可能长的子串，其中包含的0与1的个数相等。

Input

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

Output

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

Input示例

1011

Output示例

2

分析

把0当成-1，然后求前缀和。如果出现前缀和相等的，那么这个串肯定就满足要求。因为只要求最长的，所以只需要存前缀和首次出现的位置即可，之后再遇到就可以直接更新答案。

代码

#include <bits/stdc++.h> #define N 2000010 int sum[N]; char ch[N * 2]; int main() { gets(ch); memset(sum,-1,sizeof(sum)); sum[strlen(ch)] = 0; int ans = 0; int last = strlen(ch); for (int i = 0; i < strlen(ch); i++) { if (ch[i] == '0') last--; else last++; if (sum[last] > -1) ans = std::max(ans, i - sum[last] + 1); else sum[last] = i + 1; } printf("%d\n",ans); }