51nod 1391：01串

1391 01串

题目来源： Codility

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

关注

给定一个01串S,求出它的一个尽可能长的子串S[i..j]，满足存在一个位置i<=x <=j, S[i..x]中0比1多，而S[x + 1..j]中1比0多。求满足条件的最长子串长度。

Input

一行包含一个只由0和1构成的字符串S。 S的长度不超过1000000。

Output

一行包含一个整数，表示满足要求的最长子串的长度。

Input示例

Output示例

hash啊。记录出现值的第一位置，之后如果出现比这个值小于1的数，就说明这个位置到此处的位置中0比1多。

代码：

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

#define maxn 1000003

int val[maxn];
int hash_val[maxn];
int le[maxn];
int ri[maxn];

char test[maxn];

int main()
{
	//freopen("i.txt", "r", stdin);
	//freopen("o.txt", "w", stdout);

	int i, res, cur, len;

	scanf("%s", test);
	len = strlen(test);

	for (i = 0; i < len; i++)
	{
		if (test[i] == '0')
		{
			val[i] = -1;
		}
		else
		{
			val[i] = 1;
		}
	}

	memset(hash_val, -1, sizeof(hash_val));
	cur = 0;
	for (i = 0; i < len; i++)
	{
		cur = cur + val[i];
		if (cur < 0)
		{
			le[i] = i + 1;
		}
		else
		{
			if (hash_val[cur + 1] != -1)
			{
				le[i] = i - hash_val[cur + 1];
			}
			else
			{
				hash_val[cur] = i;
				le[i] = 0;
			}
		}
	}

	memset(hash_val, -1, sizeof(hash_val));
	cur = 0;
	for (i = len - 1; i >= 0; i--)
	{
		cur = cur + val[i];
		if (cur > 0)
		{
			ri[i] = len - i;
		}
		else
		{
			if (hash_val[-(cur - 1)] != -1)
			{
				ri[i] = hash_val[-(cur - 1)] - i;
			}
			else
			{
				hash_val[-(cur)] = i;
				ri[i] = 0;
			}
		}
	}
	res = 0;
	for (i = 0; i < len; i++)
	{
		if (le[i] > 0 && ri[i + 1] > 0)
			res = max(res, le[i] + ri[i + 1]);
	}
	printf("%d
", res);
	//system("pause");
	return 0;
}