Cuente substrings únicas de una string S presente en una string envolvente

Dada una string S que es una string envolvente infinita de la string “abcdefghijklmnopqrstuvwxyz” , la tarea es contar el número de substrings únicas no vacías de una string p que están presentes en s .

Ejemplos:

Entrada: S = “zab”
Salida: 6
Explicación: Todas las substrings posibles son “z”, “a”, “b”, “za”, “ab”, “zab”.

Entrada: S = “cac”
Salida: 2
Explicación: Todas las substrings posibles son solo “a” y “c”.

Enfoque: siga los pasos a continuación para resolver el problema

1. Iterar sobre cada carácter de la string
2. Inicialice una array auxiliar arr[] de tamaño 26 para almacenar la longitud actual de la substring que está presente en la string S a partir de cada carácter de la string P .
3. Inicialice una variable, digamos curLen , que almacena la longitud de la substring presente en P , incluido el carácter actual si el carácter actual no es parte de la substring anterior.
4. Inicialice una variable, digamos ans , para almacenar el recuento único de substrings no vacías de p presentes en S .
5. Repita los caracteres de la string y verifique los dos casos siguientes:
   • Compruebe si el carácter actual se puede agregar con la substring anterior para formar la substring requerida o no.
   • Agregue la diferencia de curLen y arr[curr] a ans if (curLen + 1) es mayor que arr[curr] para evitar la repetición de substrings.
6. Imprime el valor de ans .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count of
// non-empty substrings of p present in s
int findSubstringInWraproundString(string p)
{
    // Stores the required answer
    int ans = 0;
 
    // Stores the length of
    // substring present in p
    int curLen = 0;
 
    // Stores the current length
    // of substring that is
    // present in string s starting
    // from each character of p
    int arr[26] = { 0 };
 
    // Iterate over the characters of the string
    for (int i = 0; i < (int)p.length(); i++) {
 
        int curr = p[i] - 'a';
 
        // Check if the current character
        // can be added with previous substring
        // to form the required substring
        if (i > 0
            && (p[i - 1]
                != ((curr + 26 - 1) % 26 + 'a'))) {
            curLen = 0;
        }
 
        // Increment current length
        curLen++;
 
        if (curLen > arr[curr]) {
 
            // To avoid repetition
            ans += (curLen - arr[curr]);
 
            // Update arr[cur]
            arr[curr] = curLen;
        }
    }
 
    // Print the answer
    cout << ans;
}
 
// Driver Code
int main()
{
    string p = "zab";
 
    // Function call to find the
    // count of non-empty substrings
    // of p present in s
    findSubstringInWraproundString(p);
 
    return 0;
}

import java.util.*;
class GFG
{
   
    // Function to find the count of
    // non-empty substrings of p present in s
    static void findSubstringInWraproundString(String p)
    {
       
        // Stores the required answer
        int ans = 0;
 
        // Stores the length of
        // substring present in p
        int curLen = 0;
 
        // Stores the current length
        // of substring that is
        // present in string s starting
        // from each character of p
        int arr[] = new int[26];
 
        // Iterate over the characters of the string
        for (int i = 0; i < p.length(); i++)
        {
 
            int curr = p.charAt(i) - 'a';
 
            // Check if the current character
            // can be added with previous substring
            // to form the required substring
            if (i > 0
                && (p.charAt(i - 1)
                    != ((curr + 26 - 1) % 26 + 'a')))
            {
                curLen = 0;
            }
 
            // Increment current length
            curLen++;
            if (curLen > arr[curr])
            {
 
                // To avoid repetition
                ans += (curLen - arr[curr]);
 
                // Update arr[cur]
                arr[curr] = curLen;
            }
        }
 
        // Print the answer
        System.out.println(ans);
    }
 
    // Driver Code
    public static void main(String args[])
    {
        String p = "zab";
 
        // Function call to find the
        // count of non-empty substrings
        // of p present in s
        findSubstringInWraproundString(p);
    }
}
 
// This code is contributed by hemanth gadarla

# Python3 program for
# the above approach
 
# Function to find the count of
# non-empty substrings of p present in s
def findSubstringInWraproundString(p) :
 
    # Stores the required answer
    ans = 0
  
    # Stores the length of
    # substring present in p
    curLen = 0
  
    # Stores the current length
    # of substring that is
    # present in string s starting
    # from each character of p
    arr = [0]*26
  
    # Iterate over the characters of the string
    for i in range(0, len(p)) :
  
        curr = ord(p[i]) - ord('a')
  
        # Check if the current character
        # can be added with previous substring
        # to form the required substring
        if (i > 0 and (ord(p[i - 1]) != ((curr + 26 - 1) % 26 + ord('a')))) :
            curLen = 0
  
        # Increment current length
        curLen += 1
  
        if (curLen > arr[curr]) :
  
            # To avoid repetition
            ans += (curLen - arr[curr])
  
            # Update arr[cur]
            arr[curr] = curLen
  
    # Print the answer
    print(ans)
     
p = "zab"
  
# Function call to find the
# count of non-empty substrings
# of p present in s
findSubstringInWraproundString(p)
 
# This code is contributed by divyeshrabadiya07.

// C# program for
// the above approach
using System;
class GFG
{
 
  // Function to find the count of
  // non-empty substrings of p present in s
  static void findSubstringInWraproundString(string p)
  {
     
    // Stores the required answer
    int ans = 0;
 
    // Stores the length of
    // substring present in p
    int curLen = 0;
 
    // Stores the current length
    // of substring that is
    // present in string s starting
    // from each character of p
    int[] arr = new int[26];
 
    // Iterate over the characters of the string
    for (int i = 0; i < (int)p.Length; i++)
    {
      int curr = p[i] - 'a';
 
      // Check if the current character
      // can be added with previous substring
      // to form the required substring
      if (i > 0 && (p[i - 1] != ((curr + 26 - 1) % 26 + 'a')))
      {
        curLen = 0;
      }
 
      // Increment current length
      curLen++;
      if (curLen > arr[curr])
      {
 
        // To avoid repetition
        ans += (curLen - arr[curr]);
 
        // Update arr[cur]
        arr[curr] = curLen;
      }
    }
 
    // Print the answer
    Console.Write(ans);
  }
 
  // Driver code
  static void Main()
  {
    string p = "zab";
 
    // Function call to find the
    // count of non-empty substrings
    // of p present in s
    findSubstringInWraproundString(p);
  }
}
 
// This code is contributed by divyesh072019.

<script>
    // Javascript program for the above approach
     
      // Function to find the count of
    // non-empty substrings of p present in s
    function findSubstringInWraproundString(p)
    {
 
      // Stores the required answer
      let ans = 0;
 
      // Stores the length of
      // substring present in p
      let curLen = 0;
 
      // Stores the current length
      // of substring that is
      // present in string s starting
      // from each character of p
      let arr = new Array(26);
      arr.fill(0);
 
      // Iterate over the characters of the string
      for (let i = 0; i < p.length; i++)
      {
        let curr = p[i].charCodeAt() - 'a'.charCodeAt();
 
        // Check if the current character
        // can be added with previous substring
        // to form the required substring
        if (i > 0 && (p[i - 1].charCodeAt() != ((curr + 26 - 1) % 26 + 'a'.charCodeAt())))
        {
          curLen = 0;
        }
 
        // Increment current length
        curLen++;
        if (curLen > arr[curr])
        {
 
          // To avoid repetition
          ans += (curLen - arr[curr]);
 
          // Update arr[cur]
          arr[curr] = curLen;
        }
      }
 
      // Print the answer
      document.write(ans);
    }
     
    let p = "zab";
  
    // Function call to find the
    // count of non-empty substrings
    // of p present in s
    findSubstringInWraproundString(p);
   
  // This code is contributed by surehs07.
</script>

6

Complejidad temporal: O(N)
Espacio auxiliar: O(1)