Benature
0%

01子串计数

Posted on Edited on

01子串计数

题目

一个字符串的子串表示原字符串中一段连续的部分。例如，字符串”121”的子串总共有六个，它们分别是”1”(前一个),”2”,”1”(后一个),”12”,”21”和”121”。但”11”不是”121”的子串，因为两个’1’在原串中不连续。我们认为空串也不是子串。

现给你一个只含有’0’和’1’两种字符的字符串，问它含有相同’0’和’1’的字串有几个。

例如，字符串”0101”中符合条件的子串有4个。它们分别是”01”(前一个),”10”,”01”(后一个),”0101”；字符串”00110011”中符合条件的子串分别为”01”(前一个),”10”,”01”(后一个),”0011”(前一个),”0110”,”1100”,”1001”,”0011”(后一个),”011001”,”00110011”，共10个。

解答

二重循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<stdio.h>
#include<stdlib.h>
#include <string.h>

int main(){
    char str[1000000];
    scanf("%s", str);
    int count=0;
    int zero, one;
    for (int i=0; i<strlen(str); i++){
        zero = 0, one = 0;
        for (int j=i; j<L; j++){
            if (str[j] == '0'){
                zero++;
            }else if(str[j] == '1'){
                one++;
            }

            if ((j-i)%2==1){
                // judge
                if (one == zero){
                    count++;
                }
            }
        }
    }
    printf("%d\n", count);
}

一重循环

c++ 版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define score(ch) (ch == '1' ? 1 : -1)
long int count_substring_fast(char *str)
{
    unsigned int n = strlen(str);
    long int ans = 0;
    long int *counter = new long int[2 * n + 1](); // initialize
    long int tmp_sum = 0;
    for (int i = 0; i < n; ++i)
    {
        tmp_sum += score(str[i]);
        if (tmp_sum == 0)
        {
            ans++;
        }
        printf("%ld, ", tmp_sum);
        counter[n + tmp_sum]++; // 哈希
    }
    printf("\n");
    for (int i = 0; i < 2 * n + 1; ++i)
    {
        if (counter[i])
        { // 不考虑计数为 0 的
            printf("%d: %ld, %ld\n", i - n, counter[i], ans);
            ans += ((counter[i]) * (counter[i] - 1) / 2);
        }
    }
    delete[] counter;
    return ans;
}

C 版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
long int count_substring_fast(char *str)
{
    int n = strlen(str);
    long int ans = 0;
    long int *counter;
    long int tmp_sum = 0;
    counter = (long int *)malloc(sizeof(long int) * (2 * n + 1));
    for (int i = 0; i < 2 * n + 1; i++)
    {
        counter[i] = 0; // 初始化
    }

    for (int i = 0; i < n; ++i)
    {
        if (str[i] == '\0')
        {
            break;
        }
        if (str[i] == '1')
        {
            tmp_sum++;
        }
        else if (str[i] == '0')
        {
            tmp_sum--;
        }
        // tmp_sum += score(str[i]);
        if (tmp_sum == 0)
        {
            ans++;
        }
        counter[n + tmp_sum]++; // 哈希
    }
    for (int i = 0; i < 2 * n + 1; ++i)
    {
        if (counter[i])
        { // 不考虑计数为 0 的
            ans += ((counter[i]) * (counter[i] - 1) / 2);
        }
    }
    free(counter);
    counter = NULL;
    return ans;
}

reference:
https://howardlau.me/programming/zero-one-substring.html