Tutorialspoint.dev

Find all the patterns of “1(0+)1” in a given string | SET 1(General Approach)

A string contains patterns of the form 1(0+)1 where (0+) represents any non-empty consecutive sequence of 0’s. Count all such patterns. The patterns are allowed to overlap.

Note : It contains digits and lowercase characters only. The string is not necessarily a binary. 100201 is not a valid pattern.
One approach to solve the problem is discussed here, other using Regular expressions is given in Set 2
Examples:

Input : 1101001
Output : 2

Input : 100001abc101
Output : 2


Let size of input string be n.
1. Iterate through index ‘0’ to ‘n-1’.
2. If we encounter a ‘1’, we iterate till the elements are ‘0’.
3. After the stream of zeros ends, we check whether we encounter a ‘1’ or not.
4. Keep on doing this till we reach the end of string.

Below is the implementation of the above method.

C++



/* Code to count 1(0+)1 patterns in a string */
#include <bits/stdc++.h>
using namespace std;
  
/* Function to count patterns */
int patternCount(string str)
{
    /* Variable to store the last character*/
    char last = str[0];
  
    int i = 1, counter = 0;
    while (i < str.size())
    {
        /* We found 0 and last character was '1',
          state change*/
        if (str[i] == '0' && last == '1')
        {
            while (str[i] == '0')
                i++;
  
            /* After the stream of 0's, we got a '1',
               counter incremented*/
            if (str[i] == '1')
                counter++;
        }
  
        /* Last character stored */
        last = str[i];
        i++;
    }
  
    return counter;
}
  
/* Driver Code */
int main()
{
    string str = "1001ab010abc01001";
    cout << patternCount(str) << endl;
    return 0;
}

Java

// Java Code to count 1(0+)1 
// patterns in a string 
import java.io.*;
  
class GFG 
{
    // Function to count patterns 
    static int patternCount(String str)
    {
        /* Variable to store the last character*/
        char last = str.charAt(0);
      
        int i = 1, counter = 0;
        while (i < str.length())
        {
            /* We found 0 and last character was '1',
            state change*/
            if (str.charAt(i) == '0' && last == '1')
            {
                while (str.charAt(i) == '0')
                    i++;
      
                // After the stream of 0's, we 
                // got a '1',counter incremented
                if (str.charAt(i) == '1')
                    counter++;
            }
      
            /* Last character stored */
            last = str.charAt(i);
            i++;
        }
      
        return counter;
    }
      
    // Driver Code 
    public static void main (String[] args)
    {
        String str = "1001ab010abc01001";
        System.out.println(patternCount(str));
          
    }
}
  
// This code is contributed by vt_m.

Python3

# Python3 code to count 1(0+)1 patterns in a 
  
# Function to count patterns 
def patternCount(str):
      
    # Variable to store the last character
    last = str[0]
  
    i = 1; counter = 0
    while (i < len(str)):
          
        # We found 0 and last character was '1',
        # state change
        if (str[i] == '0' and last == '1'):
            while (str[i] == '0'):
                i += 1
                  
                # After the stream of 0's, we got a '1',
                # counter incremented
                if (str[i] == '1'): 
                    counter += 1
          
        # Last character stored 
        last = str[i]
        i += 1
      
    return counter
  
  
# Driver Code 
str = "1001ab010abc01001"
ans = patternCount(str)
print (ans)
      
# This code is contributed by saloni1297

C#

// C# Code to count 1(0 + )1 
// patterns in a string 
using System;
  
class GFG 
{
      
    // Function to count patterns 
    static int patternCount(String str)
    {
        // Variable to store the 
        // last character
        char last = str[0];
      
        int i = 1, counter = 0;
        while (i < str.Length)
        {
            // We found 0 and last 
            // character was '1',
            // state change
            if (str[i] == '0' && last == '1')
            {
                while (str[i] == '0')
                    i++;
      
                // After the stream of 0's, we 
                // got a '1',counter incremented
                if (str[i] == '1')
                    counter++;
            }
      
            // Last character stored 
            last = str[i];
            i++;
        }
      
        return counter;
    }
      
    // Driver Code 
    public static void Main ()
    {
        String str = "1001ab010abc01001";
        Console.Write(patternCount(str));
          
    }
}
  
// This code is contributed by nitin mittal

PHP

<?php
// PHP Code to count 1(0+)1 patterns 
// in a string
  
// Function to count patterns
function patternCount($str)
{
      
    // Variable to store the 
    // last character
    $last = $str[0];
  
    $i = 1; 
    $counter = 0;
    while ($i < strlen($str))
    {
          
        // We found 0 and last character
        // was '1', state change
        if ($str[$i] == '0' && $last == '1')
        {
            while ($str[$i] == '0')
                $i++;
  
            // After the stream of 0's,
            // we got a '1', counter 
            // incremented
            if ($str[$i] == '1')
                $counter++;
        }
  
        /* Last character stored */
        $last = $str[$i];
        $i++;
    }
  
    return $counter;
}
  
    // Driver Code
    $str = "1001ab010abc01001";
    echo patternCount($str) ;
  
// This code is contributed by nitin mittal
?>


Output :

2

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter