51nod 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;

}

巴特西

51nod 1393：0和1相等串

最新文章

热门文章