51nod 1393 0和1相等串

1393 0和1相等串

基准时间限制：1 秒空间限制：131072 KB 分值: 20 难度：3级算法题

关注

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

Input

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

Output

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

Input示例

Output示例

求最长的子串使的0和1的数量相等，o(n)算法。1就加1,0就减一，遍历一遍后就是就相同数之间的最大间隔了。

比如 0 1 0 1 0 1 0 1 1 1 0 0

0 -1 0 -1 0 -1 0 -1 0 1 2 1 0

里面有-1、0、1、2。-1 的最大间隔是第一个-1和最后一个-1，即6。0的话是12。1 的话是2。2 没有值。

所以答案是12。所以每个值只要储存第一个的位置，然后没遇见一个就与第一个相减去最大值就可以了。

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 1000010;
 5 char str[N];
 6 int main() {
 7     map<int,int> mp;
 8     cin >> str+1;
 9     int ans = 0, cnt = 0;
10     for(int i = 1; str[i]; i ++) {
11         if(str[i]-'0') cnt++;
12         else cnt--;
13         if(cnt == 0) ans = i;
14         else{
15             if(mp[cnt]) ans = max(ans,i-mp[cnt]);
16             else mp[cnt] = i;
17             // cout << mp[cnt] << ' ' << cnt << endl;
18         }
19     }
20     cout << ans << endl;
21     return 0;
22 }