首页 > 代码库 > 1393 0和1相等串 51nod

1393 0和1相等串 51nod

1393 0和1相等串技术分享
基准时间限制:1 秒 空间限制:131072 KB 分值: 20 难度:3级算法题
技术分享 收藏
技术分享 关注
给定一个0-1串,请找到一个尽可能长的子串,其中包含的0与1的个数相等。
Input
一个字符串,只包含01,长度不超过1000000。
Output
一行一个整数,最长的0与1的个数相等的子串的长度。
Input示例
1011
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\n", ans);
}

 

1393 0和1相等串 51nod