1393 0和1相等串 51nod

1393 0和1相等串

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

关注

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

Input

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

Output

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

Input示例

Output示例

2

起点和终点的关系整理一下，有时候可以得到一种hash的思路。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<queue>
#include<deque>
#include<iomanip>
#include<vector>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<fstream>
#include<memory>
#include<list>
#include<string>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAXN 1000009
#define N 21
#define MOD 1000000
#define INF 1000000009
const double eps = 1e-8;
const double PI = acos(-1.0);
/*
如果 从位置i 到位置j是一段 01相等子串
设 n0[] 为0的数目，n1为1的数目
那么有 n1[i] - n1[j] == n0[i] - n0[j]
整理可得  n1[i] - n0[i] == n1[j] - n0[j]
那么可以记录路径上所有n1[i] - n0[i]的值（map,hash)
当后面重复 该值（出现相等子串） 可以取最大值
*/
map<int, int> M;
char s[MAXN];
int n1[MAXN], n0[MAXN];
int main()
{
    int l, ans = 0;
    scanf("%s", s);
    l = strlen(s);
    if (s[0] == '1')
        n1[0] = 1, n0[0] = 0;
    else
        n0[0] = 1, n1[0] = 0;
    M[n1[0] - n0[0]] = 0;
    M[0] = -1;
    for (int i = 1; i < l; i++)
    {
        if (s[i] == '1')
            n1[i] = n1[i - 1] + 1, n0[i] = n0[i - 1];
        else
            n0[i] = n0[i - 1] + 1, n1[i] = n1[i - 1];
        if (M.find(n1[i] - n0[i]) == M.end())
            M[n1[i] - n0[i]] = i;
        else
            ans = max(ans, i - M[n1[i] - n0[i]]);
    }
    printf("%d
", ans);
}