01子串计数

Posted on Views: Valine:

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
#include<stdio.h>
2
#include<stdlib.h>
3
#include <string.h>
4
5
int main(){
6
    char str[1000000];
7
    scanf("%s", str);
8
    int count=0;
9
    int zero, one;
10
    for (int i=0; i<strlen(str); i++){
11
        zero = 0, one = 0;
12
        for (int j=i; j<L; j++){
13
            if (str[j] == '0'){
14
                zero++;
15
            }else if(str[j] == '1'){
16
                one++;
17
            }
18
19
            if ((j-i)%2==1){
20
                // judge
21
                if (one == zero){
22
                    count++;
23
                }
24
            }
25
        }
26
    }
27
    printf("%d\n", count);
28
}

一重循环

c++ 版本

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

C 版本

1
long int count_substring_fast(char *str)
2
{
3
    int n = strlen(str);
4
    long int ans = 0;
5
    long int *counter;
6
    long int tmp_sum = 0;
7
    counter = (long int *)malloc(sizeof(long int) * (2 * n + 1));
8
    for (int i = 0; i < 2 * n + 1; i++)
9
    {
10
        counter[i] = 0; // 初始化
11
    }
12
13
    for (int i = 0; i < n; ++i)
14
    {
15
        if (str[i] == '\0')
16
        {
17
            break;
18
        }
19
        if (str[i] == '1')
20
        {
21
            tmp_sum++;
22
        }
23
        else if (str[i] == '0')
24
        {
25
            tmp_sum--;
26
        }
27
        // tmp_sum += score(str[i]);
28
        if (tmp_sum == 0)
29
        {
30
            ans++;
31
        }
32
        counter[n + tmp_sum]++; // 哈希
33
    }
34
    for (int i = 0; i < 2 * n + 1; ++i)
35
    {
36
        if (counter[i])
37
        { // 不考虑计数为 0 的
38
            ans += ((counter[i]) * (counter[i] - 1) / 2);
39
        }
40
    }
41
    free(counter);
42
    counter = NULL;
43
    return ans;
44
}

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