Recuento de ocurrencias de un patrón «1(0+)1» en una string

Dada una string alfanumérica, encuentre el número de veces que ocurre un patrón 1(0+)1 en la string dada. Aquí, (0+) significa la presencia de una secuencia no vacía de 0 consecutivos.

Ejemplos: 

Input : 1001010001
Output : 3
First sequence is in between 0th and 3rd index.
Second sequence is in between 3rd and 5th index.
Third sequence is in between 5th and 9th index.
So total number of sequences comes out to be 3.

Input : 1001ab010abc01001
Output : 2
First sequence is in between 0th and 3rd index.
Second valid sequence is in between 13th and 16th
index. So total number of sequences comes out to 
be 2.

La idea para resolver este problema es primero encontrar un ‘1’ y seguir avanzando en la string y verificar como se menciona a continuación: 

1. Si se obtiene cualquier carácter que no sea ‘0’ y ‘1’, significa que el patrón no es válido. Entonces continuamos en la búsqueda del siguiente ‘1’ de este índice y repetimos estos pasos nuevamente. 
2. Si se ve un ‘1’, verifique la presencia de un ‘0’ en la posición anterior para verificar la validez de la secuencia.

A continuación se muestra la implementación de la idea anterior: 

// C++ program to calculate number of times
// the pattern occurred in given string
#include<iostream>
using namespace std;
 
// Returns count of occurrences of "1(0+)1"
// int str.
int countPattern(string str)
{
    int len = str.size();
    bool oneSeen = 0;
 
    int count = 0;  // Initialize result
    for (int i = 0; i < len ; i++)
    {
 
        // Check if encountered '1' forms a valid
        // pattern as specified
        if (str[i] == '1' && oneSeen == 1)
            if (str[i - 1] == '0')
                count++;
 
        // if 1 encountered for first time
        // set oneSeen to 1
        if (str[i] == '1' && oneSeen == 0)
           {
            oneSeen = 1;
            continue;
           }
        // Check if there is any other character
        // other than '0' or '1'. If so then set
        // oneSeen to 0 to search again for new
        // pattern
        if (str[i] != '0' && str[i] != '1')
            oneSeen = 0;
 
 
    }
 
    return count;
}
 
// Driver program to test above function
int main()
{
    string str = "100001abc101";
    cout << countPattern(str);
    return 0;
}

//Java program to calculate number of times
//the pattern occurred in given string
public class GFG
{
    // Returns count of occurrences of "1(0+)1"
    // int str.
    static int countPattern(String str)
    {
        int len = str.length();
        boolean oneSeen = false;
         
        int count = 0;  // Initialize result
        for(int i = 0; i < len ; i++)
        {
            char getChar = str.charAt(i);
             
            // Check if encountered '1' forms a valid
            // pattern as specified
            if (getChar == '1' && oneSeen == true){
                if (str.charAt(i - 1) == '0')
                    count++;
            }
 
            // if 1 encountered for first time
            // set oneSeen to 1
            if(getChar == '1' && oneSeen == false)
                oneSeen = true;
             
            // Check if there is any other character
            // other than '0' or '1'. If so then set
            // oneSeen to 0 to search again for new
            // pattern
            if(getChar != '0' && str.charAt(i) != '1')
                oneSeen = false;
             
 
        }
        return count;
    }
 
    // Driver program to test above function
    public static void main(String[] args)
    {
         String str = "100001abc101";
         System.out.println(countPattern(str));
    }
 
}
// This code is contributed by Sumit Ghosh

# Python program to calculate number of times
# the pattern occurred in given string
 
# Returns count of occurrences of "1(0+)1"
def countPattern(s):
    length = len(s)
    oneSeen = False
     
    count = 0   # Initialize result
    for i in range(length):
 
        # Check if encountered '1' forms a valid
        # pattern as specified
        if (s[i] == '1' and oneSeen):
            if (s[i - 1] == '0'):
                count += 1
 
        # if 1 encountered for first time
        # set oneSeen to 1
        if (s[i] == '1' and oneSeen == 0):
            oneSeen = True
  
        # Check if there is any other character
        # other than '0' or '1'. If so then set
        # oneSeen to 0 to search again for new
        # pattern
        if (s[i] != '0' and s[i] != '1'):
            oneSeen = False
  
 
  
    return count
 
# Driver code
s = "100001abc101"
print(countPattern(s))
 
# This code is contributed by Sachin Bisht

// C# program to calculate number
// of times the pattern occurred
// in given string
using System;
 
class GFG
{
// Returns count of occurrences
// of "1(0+)1" int str.
public static int countPattern(string str)
{
    int len = str.Length;
    bool oneSeen = false;
 
    int count = 0; // Initialize result
    for (int i = 0; i < len ; i++)
    {
        char getChar = str[i];
 
        // Check if encountered '1' forms
        // a valid pattern as specified
        if (getChar == '1' &&
                 oneSeen == true)
        {
            if (str[i - 1] == '0')
            {
                count++;
            }
        }
 
        // if 1 encountered for first
        // time set oneSeen to 1
        if (getChar == '1' &&
            oneSeen == false)
        {
            oneSeen = true;
        }
 
        // Check if there is any other character
        // other than '0' or '1'. If so then set
        // oneSeen to 0 to search again for new
        // pattern
        if (getChar != '0' &&
                 str[i] != '1')
        {
            oneSeen = false;
        }
 
 
    }
    return count;
}
 
// Driver Code
public static void Main(string[] args)
{
    string str = "100001abc101";
    Console.WriteLine(countPattern(str));
}
 
}
 
// This code is contributed
// by Shrikant13

<?php
// PHP program to calculate number of times
// the pattern occurred in given string
 
// Returns count of occurrences
// of "1(0+)1"
function countPattern($str)
{
    $len = strlen($str);
    $oneSeen = 0;
 
    $count = 0; // Initialize result
    for ($i = 0; $i < $len ; $i++)
    {
        // Check if encountered '1' forms a
        // valid pattern as specified
        if ($str[$i] == '1' && $oneSeen == 1)
            if ($str[$i - 1] == '0')
                $count++;
 
        // if 1 encountered for first
        // time set oneSeen to 1
        if ($str[$i] == '1' && $oneSeen == 0)
            $oneSeen = 1;
 
        // Check if there is any other character
        // other than '0' or '1'. If so then set
        // oneSeen to 0 to search again for new
        // pattern
        if ($str[$i] != '0' && $str[$i] != '1')
            $oneSeen = 0;
 
 
    }
 
    return $count;
}
 
// Driver Code
$str = "100001abc101";
echo countPattern($str);
 
// This code is contributed
// by ChitraNayal
?>

<script>
//Javascript program to calculate number of times
//the pattern occurred in given string
     
    // Returns count of occurrences of "1(0+)1"
    // int str.
    function countPattern(str)
    {
        let len = str.length;
        let oneSeen = false;
           
        let count = 0;  // Initialize result
        for(let i = 0; i < len ; i++)
        {
            let getChar = str[i];
               
            // Check if encountered '1' forms a valid
            // pattern as specified
            if (getChar == '1' && oneSeen == true){
                if (str[i-1] == '0')
                    count++;
            }
   
            // if 1 encountered for first time
            // set oneSeen to 1
            if(getChar == '1' && oneSeen == false)
                oneSeen = true;
               
            // Check if there is any other character
            // other than '0' or '1'. If so then set
            // oneSeen to 0 to search again for new
            // pattern
            if(getChar != '0' && str[i] != '1')
                oneSeen = false;
               
   
        }
        return count;
    }
     
    // Driver program to test above function
    let str = "100001abc101";
    document.write(countPattern(str));
     
    //This code is contributed by avanitrachhadiya2155
     
</script>

2

Complejidad de tiempo: O( N ) , donde N es la longitud de la string de entrada.
Espacio auxiliar: O(1) , ya que no se requiere espacio adicional

Este artículo es una contribución de Sakshi Tiwari . Si te gusta GeeksforGeeks (¡sabemos que te gusta!) 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.