计数二进制子串_计数子串

蔚落 2023-03-05 09:37 36阅读 0赞

计数二进制子串

**Problem statement:**

**问题陈述：**

**Given a binary string find the number of substring** that can formed such that every substring starts with **'1'** and ends with **'1'**.

**给定一个二进制字符串，找到**可以形成**的子字符串数，**以使每个子字符串均以**'1'**开头并以**'1'**结束。

**Example:**

**例：**

Input string:
        100110100
    
        Output:
        6
    
        Explanation:
        Substrings those start with '1' and end with '1'.
        1001
        10011
        1001101
        11
        1101
        101
        N.B: Don't think that substrings are: 1001 11 101 These only

**Algorithm:**

**算法：**

Though it's a string problem, it can be solved actually using simple combinatorics.

尽管这是一个字符串问题，但实际上可以使用简单的组合方法解决。

1.  Calculate total no of '1' occurring in the string
    
    计算字符串中出现的总数“ 1”
2.      Set count 0; (count is to store frequency of '1')
        For each character at index i of the string
            IF(string[i]=='1')
                Increment count;
            END IF
        END FOR
3.  Now we have total number of '1'. Finding no of substring starting with '1' & ending with '1' is equivalent of choosing two '1's out of total no of '1's (count). We are not at all bothered how many zeros are in between those two '1'. In fact, there can be '1's in between those two '1's picked up.
    
    现在我们的总数为1。 找到以“ 1”开头和以“ 1”结尾的子串的编号等同于从“ 1”(总数)的总编号中选择两个“ 1”。 我们根本不会理会这两个“ 1”之间有多少个零。 实际上，在这两个“ 1”之间可能存在“ 1”。
    
    Thus,
    
    从而，
    
    number of substrings starting with '1' & ending with '1'
    
    以“ 1”开头并以“ 1”结尾的子字符串数
    
    ![ex: count substring 1][ex_ count substring 1], where
    
    ***count*** is the frequency of '1's in the string.
    
    ***count***是字符串中“ 1”的频率。
    
    ![ex: count substring 2][ex_ count substring 2]

So for our above example:

因此，对于我们上面的示例：

Input string:
        100110100
        Number of '1's=4
        Thus total number of substrings that can be formed 
        starting with '1' & ending with '1' = (4*3)/2 = 6

**C++ implementation:**

**C ++实现：**

#include <bits/stdc++.h>
    using namespace std;
    
    int compute(string s){
        
    	int count=0;
    	//counting no of '1's
    	for(int i=0;i<s.length();i++)
    		if(s[i]=='1')
    			count++;
    	//returning count choose 2
    	return (count*(count-1))/2;
    }
    
    int main(){
        
    	string s;
    
    	cout<<"enter your input string(binary string)\n";
    	cin>>s;
    
    	cout<<"no of substrings starting with '1' &";
    	cout<<" ending with '1' is: "<<compute(s)<<endl;
    
    	return 0;
    }

**Output**

**输出量**

enter your input string(binary string)
    100110100
    no of substrings starting with '1' & ending with '1' is: 6

> 翻译自: [https://www.includehelp.com/icp/count-substrings.aspx][https_www.includehelp.com_icp_count-substrings.aspx]

计数二进制子串

[ex_ count substring 1]: /images/20230208/fa4395a5e7d9493ba4733d07324ee704.png
[ex_ count substring 2]: https://www.includehelp.com/icp/Images/count-substrings-1.jpg
[https_www.includehelp.com_icp_count-substrings.aspx]: https://www.includehelp.com/icp/count-substrings.aspx