Programa de Python 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. 

# Python3 program to check if 
# a string is substring of other.
  
# Returns true if s1 is substring 
# of s2
def isSubstring(s1, s2):
    M = len(s1)
    N = len(s2)
  
    # A loop to slide pat[] one by one 
    for i in range(N - M + 1):
  
        # For current index i,
        # check for pattern match 
        for j in range(M):
            if (s2[i + j] != s1[j]):
                break
              
        if j + 1 == M :
            return i
  
    return -1
  
# Driver Code
if __name__ == "__main__":
    s1 = "for"
    s2 = "geeksforgeeks"
    res = isSubstring(s1, s2)
    if res == -1 :
        print("Not present")
    else:
        print("Present at index " + str(res))
# This code is contributed by ChitraNayal

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.

# Python3 program for the above approach
def Substr(Str, target):
      
    t = 0
    Len = len(Str)
    i = 0
      
    # Iterate from 0 to Len - 1
    for i in range(Len):
        if (t == len(target)):
            break
        if (Str[i] == target[t]):
            t += 1
        else:
            t = 0
              
    if (t < len(target)):
        return -1
    else:
        return (i - t)
  
# Driver code
print(Substr("GeeksForGeeks", "Fr"))
print(Substr("GeeksForGeeks", "For"))
  
# This code is contributed by avanitrachhadiya2155

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.