Programa Php 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. 

PHP

<?php
// PHP program to check if a 
// string is substring of other.
  
// Returns true if s1 is substring 
// of s2
function isSubstring($s1, $s2)
{
    $M = strlen($s1);
    $N = strlen($s2);
  
    // A loop to slide
    // pat[] one by one 
    for ($i = 0; $i <= $N - $M; $i++) 
    {
        $j = 0;
  
        // For current index i, 
        // check for pattern match
        for (; $j < $M; $j++)
            if ($s2[$i + $j] != $s1[$j])
                break;
  
        if ($j == $M)
            return $i;
    }
  
    return -1;
}
  
// Driver Code
$s1 = "for";
$s2 = "geeksforgeeks";
$res = isSubstring($s1, $s2);
if ($res == -1)
    echo "Not present";
else
    echo "Present at index " . $res;
  
// This code is contributed by mits
?>

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.
Consulte el artículo completo sobre Comprobar si una string es una substring de otra para obtener más detalles.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *