Programa C++ para verificar si una string es una substring de otra

Dadas dos strings s1 y s2, encuentre si s1 es una substring de s2. En caso afirmativo, devuelve el índice de la primera aparición, de lo contrario, devuelve -1.

Ejemplos: 

Input: s1 = "for", s2 = "geeksforgeeks"
Output: 5
Explanation:
String "for" is present as a substring
of s2.

Input: s1 = "practice", s2 = "geeksforgeeks"
Output: -1.
Explanation:
There is no occurrence of "practice" in
"geeksforgeeks"

Enfoque simple: la idea es ejecutar un ciclo de principio a fin y para cada índice en la string dada, verifique si la substring se puede formar a partir de ese índice. Esto se puede hacer ejecutando un bucle anidado que atraviese la string dada y, en ese bucle, ejecute otro bucle que busque substrings de cada índice. 
Por ejemplo, considere que hay una string de longitud N y una substring de longitud M. Luego ejecute un ciclo anidado, donde el ciclo externo va de 0 a (NM) y el ciclo interno de 0 a M. Para un índice muy verificado si la substring atravesada por el bucle interno es la substring dada o no. 

// C++ program to check if a string is
// substring of other.
#include <bits/stdc++.h>
using namespace std;
  
// Returns true if s1 is substring 
// of s2
int isSubstring(string s1, string s2)
{
    int M = s1.length();
    int N = s2.length();
  
    /* A loop to slide pat[] one 
       by one */
    for (int i = 0; i <= N - M; i++) 
    {
        int j;
  
        /* For current index i, check for
           pattern match */
        for (j = 0; j < M; j++)
            if (s2[i + j] != s1[j])
                break;
  
        if (j == M)
            return i;
    }
    return -1;
}
  
// Driver code 
int main()
{
    string s1 = "for";
    string s2 = "geeksforgeeks";
    int res = isSubstring(s1, s2);
    if (res == -1)
        cout << "Not present";
    else
        cout << "Present at index " << 
                 res;
    return 0;
}

Producción:

Present at index 5

Análisis de Complejidad: 

• Complejidad temporal: O(m * n) donde m y n son longitudes de s1 y s2 respectivamente. 
  Se utiliza un bucle anidado, el bucle exterior va de 0 a NM y el bucle interior de 0 a M, por lo que la complejidad es O(m*n).
• Complejidad espacial: O(1). 
  Como no se requiere espacio adicional.

Una solución eficiente es utilizar un algoritmo de búsqueda O(n) como el algoritmo KMP , el algoritmo Z , etc.
Implementaciones del lenguaje: 

• Substring de Java
• substr en C++
• python encontrar

Otra solución eficiente: 

• Una solución eficiente necesitaría solo un recorrido, es decir, O(n) en la string más larga s1. Aquí comenzaremos a recorrer la string s1 y mantendremos un puntero para la string s2 desde el índice 0.
• Para cada iteración, comparamos el carácter actual en s1 y lo verificamos con el puntero en s2.
• Si coinciden, incrementamos el puntero en s2 en 1. Y por cada discrepancia, volvemos a establecer el puntero en 0.
• También controle cuando el valor del puntero s2 sea igual a la longitud de la string s2, si es verdadero, rompemos y devolvemos el valor (puntero de la string s1 – puntero de la string s2)
• Funciona con strings que contienen caracteres duplicados.

// C++ program to implement 
// the above approach
#include <bits/stdc++.h>
using namespace std;
  
int Substr(string s2, string s1)
{
    // pointing s2
    int counter = 0; 
    int i = 0;
    for(; i < s1.length(); i++)
    {
        if(counter==s2.length())
            break;
        if(s2[counter]==s1[i])
        {
            counter++;
        }
      else
        {
            // Special case where character preceding 
            // the i'th character is duplicate
            if(counter > 0)
            {
                i -= counter;
            }
            counter = 0;
        }
    }
    return (counter < s2.length() ? 
            -1 : i - counter);
}
  
// Driver code
int main() 
{
    string s1 = 
    "geeksfffffoorrfoorforgeeks";
    cout << Substr("for", s1);
    return 0;
}
// This code is contributed by Manu Pathria

Producción:

18

Análisis de Complejidad:

La complejidad del código anterior seguirá siendo O(n*m) en el peor de los casos y la complejidad del espacio será O(1).

Consulte el artículo completo sobre Comprobar si una string es una substring de otra para obtener más detalles.