Encuentra todos los patrones de “1(0+)1” en una string dada | SET 1 (Enfoque general)

Una string contiene patrones de la forma 1(0+)1 donde (0+) representa cualquier secuencia consecutiva no vacía de 0. Cuente todos esos patrones. Se permite que los patrones se superpongan.

Nota: Solo contiene dígitos y caracteres en minúsculas. La string no es necesariamente un binario. 100201 no es un patrón válido. 
Aquí se discute un enfoque para resolver el problema, otro usando expresiones regulares se da en el Conjunto 2 

Ejemplos: 

Input : 1101001
Output : 2

Input : 100001abc101
Output : 2

Deje que el tamaño de la string de entrada sea n. 

1. Iterar a través del índice ‘0’ a ‘n-1’. 
2. Si encontramos un ‘1’, iteramos hasta que los elementos sean ‘0’. 
3. Después de que termina la secuencia de ceros, verificamos si encontramos un ‘1’ o no. 
4. Sigue haciendo esto hasta que lleguemos al final de la string.

A continuación se muestra la implementación del método anterior. 

/* 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 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 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# 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 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
?>

<script>
 
// javascript Code to count 1(0+)1
// patterns in a string
 
    // Function to count patterns
    function patternCount(str)
    {
        /* Variable to store the last character*/
        var last = str.charAt(0);
     
        var 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
    var str = "1001ab010abc01001";
    document.write(patternCount(str));
 
 
// This code is contributed by 29AjayKumar
</script>

2

Este artículo es una contribución de Rohit Thapliyal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.