51nod 1393：0和1相等串

1393 0和1相等串

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

关注

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

Input

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

Output

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

Input示例

Output示例

记录每一个字符时所含有的1个个数与0的个数，一个字串包含的0和1的个数相等，就是首尾处1的个数与0的个数的差值相等。所以对于每一个字符，看之前这个差值有没有相同的，有相同的就取看能否够得着最大值。没有则标记一下。O(n)。

代码：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std;

int sum0[1000000];
int sum1[1000000];
int diff[1000000];

int main()
{
	memset(diff, -1, sizeof(diff));
	string test;
	cin >> test;
	
	int i, max_v = 0;
	int len = test.length();
	
	sum0[0] = 0;
	sum1[0] = 0;

	if (test[0] == '0')
	{
		sum0[i] = 1;
		sum1[i] = 0;
	}
	else
	{
		sum1[i] = 1;
		sum0[i] = 0;
	}

	for (i = 1; i < len; i++)
	{
		if (test[i] == '0')
		{
			sum0[i] = sum0[i - 1] + 1;
			sum1[i] = sum1[i - 1];
		}
		else
		{
			sum1[i] = sum1[i - 1] + 1;
			sum0[i] = sum0[i - 1];
		}
		if (diff[sum1[i] - sum0[i] + 500000] == -1)
		{
			diff[sum1[i] - sum0[i] + 500000] = i;
		}
		else 
		{
			max_v = max(max_v, i - diff[sum1[i] - sum0[i] + 500000]);
		}
		if (sum1[i] == sum0[i])
		{
			max_v = max(max_v, i + 1);
		}
	}
	cout << max_v << endl;

	return 0;
}