Finding a juego porciones de dos cadenas en PHP

Question

Estoy buscando una manera fácil de encontrar los correspondientes partes de dos cadenas en PHP (específicamente en el contexto de un URI)

Por ejemplo, considere las dos cadenas:

http://2.2.2.2/~machinehost/deployment_folder/

y

/~ machinehost/deployment_folder/usuarios/bob/ajustes

Lo que necesito es a cortar la porción coincidente de estas dos cadenas de la segunda cadena, dando como resultado:

usuarios/bob/ajustes

antes de añadir la primera cadena como un prefijo, formando un URI absoluto.

¿Hay alguna manera simple (en PHP) de comparar dos cadenas arbitrarias para hacer coincidir las subcadenas dentro de ellas?

EDIT: como se ha señalado, que significó la coincidencia más larga subcadena común a ambas cadenas

Answer 1

This sería la respuesta. Función PHP lista para usar.

Answer 2

No estoy seguro de entender su solicitud completa, pero la idea es:

Sea A su URL y B "/ ~ machinehost/deployment_folder/usuarios/bob/ajustes"

• búsqueda B en a -> se obtiene un índice i (donde i es la posición de la primera/de B en a)
• Sea L = longitud (A)
• Es necesario cortar B a partir de (li) de longitud (B) para agarrar la última parte de B (/ usuarios/bob/ajustes)

No he probado aún así, pero si realmente lo necesita, puedo ayudarlo a hacer que esta solución brillante (irónica) funcione.

Tenga en cuenta que puede ser posible con las expresiones regulares como

$pattern = "$B(.*?)" 
$res = array(); 
preg_match_all($pattern, $A, $res); 

Editar: Creo que su último comentario invalida mi respuesta. Pero lo que quieres es encontrar subcadenas. Por lo tanto, primero puede comenzar con un algoritmo pesado que intenta encontrar B [1: i] en A para i en {2, longitud (B)} y luego usar algunos productos dynamic programming.

Answer 3

Suponiendo sus cadenas son $a y $b, respectivamente, puede utilizar esto:

$a = 'http://2.2.2.2/~machinehost/deployment_folder/'; 
$b = '/~machinehost/deployment_folder/users/bob/settings'; 

$len_a = strlen($a); 
$len_b = strlen($b); 

for ($p = max(0, $len_a - $len_b); $p < $len_b; $p++) 
    if (substr($a, $len_a - ($len_b - $p)) == substr($b, 0, $len_b - $p)) 
     break; 

$result = $a.substr($b, $len_b - $p); 

echo $result; 

Este resultado es http://2.2.2.2/~machinehost/deployment_folder/users/bob/settings.

Answer 4

Pruebe esto.

http://pastebin.com/GqS3UiPD

Answer 5

no parece ser un fuera de la caja de código que hay para su requisito. Entonces busquemos de una manera simple.

Para este ejercicio utilicé dos métodos, uno para encontrar la coincidencia más larga, y otro para cortar la parte correspondiente.

El método FindLongestMatch(), desmonta un camino, pieza por pieza busca una coincidencia en el otro camino, manteniendo solo una coincidencia, la más larga (sin matrices, sin clasificación). El método RemoveLongestMatch() toma el sufijo o 'resto' después de la posición encontrada la coincidencia más larga.

Aquí el código fuente completo:

<?php 

function FindLongestMatch($relativePath, $absolutePath) 
{ 
    static $_separator = '/'; 
    $splitted = array_reverse(explode($_separator, $absolutePath)); 

    foreach ($splitted as &$value) 
    { 
     $matchTest = $value.$_separator.$match; 
     if(IsSubstring($relativePath, $matchTest)) 
      $match = $matchTest; 

     if (!empty($value) && IsNewMatchLonger($match, $longestMatch)) 
      $longestMatch = $match; 
    } 

    return $longestMatch; 
} 

//Removes from the first string the longest match. 
function RemoveLongestMatch($relativePath, $absolutePath) 
{ 
    $match = findLongestMatch($relativePath, $absolutePath); 
    $positionFound = strpos($relativePath, $match);  
    $suffix = substr($relativePath, $positionFound + strlen($match)); 

    return $suffix; 
} 

function IsNewMatchLonger($match, $longestMatch) 
{ 
    return strlen($match) > strlen($longestMatch); 
} 

function IsSubstring($string, $subString) 
{ 
    return strpos($string, $subString) > 0; 
} 

Se trata de un subconjunto representativo de casos de prueba:

//TEST CASES 
echo "<br>-----------------------------------------------------------"; 
echo "<br>".$absolutePath = 'http://2.2.2.2/~machinehost/deployment_folder/'; 
echo "<br>".$relativePath = '/~machinehost/deployment_folder/users/bob/settings'; 
echo "<br>Longest match: ".findLongestMatch($relativePath, $absolutePath); 
echo "<br>Suffix: ".removeLongestMatch($relativePath, $absolutePath); 

echo "<br>-----------------------------------------------------------"; 
echo "<br>".$absolutePath = 'http://1.1.1.1/root/~machinehost/deployment_folder/'; 
echo "<br>".$relativePath = '/root/~machinehost/deployment_folder/users/bob/settings'; 
echo "<br>Longest match: ".findLongestMatch($relativePath, $absolutePath); 
echo "<br>Suffix: ".removeLongestMatch($relativePath, $absolutePath); 

echo "<br>-----------------------------------------------------------"; 
echo "<br>".$absolutePath = 'http://2.2.2.2/~machinehost/deployment_folder/users/'; 
echo "<br>".$relativePath = '/~machinehost/deployment_folder/users/bob/settings'; 
echo "<br>Longest match: ".findLongestMatch($relativePath, $absolutePath); 
echo "<br>Suffix: ".removeLongestMatch($relativePath, $absolutePath); 

echo "<br>-----------------------------------------------------------"; 
echo "<br>".$absolutePath = 'http://3.3.3.3/~machinehost/~machinehost/subDirectory/deployment_folder/'; 
echo "<br>".$relativePath = '/~machinehost/subDirectory/deployment_folderX/users/bob/settings'; 
echo "<br>Longest match: ".findLongestMatch($relativePath, $absolutePath); 
echo "<br>Suffix: ".removeLongestMatch($relativePath, $absolutePath); 

Ejecución de anteriores casos de prueba proporciona el siguiente resultado:

http://2.2.2.2/~machinehost/deployment_folder/ 
/~machinehost/deployment_folder/users/bob/settings 
Longuest match: ~machinehost/deployment_folder/ 
Suffix: users/bob/settings 

http://1.1.1.1/root/~machinehost/deployment_folder/ 
/root/~machinehost/deployment_folder/users/bob/settings 
Longuest match: root/~machinehost/deployment_folder/ 
Suffix: users/bob/settings 

http://2.2.2.2/~machinehost/deployment_folder/users/ 
/~machinehost/deployment_folder/users/bob/settings 
Longuest match: ~machinehost/deployment_folder/users/ 
Suffix: bob/settings 

http://3.3.3.3/~machinehost/~machinehost/subDirectory/deployment_folder/ 
/~machinehost/subDirectory/deployment_folderX/users/bob/settings 
Longuest match: ~machinehost/subDirectory/ 
Suffix: deployment_folderX/users/bob/settings 

Tal vez puedes tomar la idea de esta pieza de código y convertirla en algo que encuentres útil f o su proyecto actual. Avísame si te funcionó. Por cierto, la respuesta de Mr. oreX también se ve bien.

Answer 6

Encontrar la coincidencia más larga en común también se puede hacer utilizando expresiones regulares.

La siguiente función tomará dos cadenas, use una para crear una expresión regular y ejecútela contra la otra.

/** 
* Determine the longest common match within two strings 
* 
* @param string $str1 
* @param string $str2 Two strings in any order. 
* @param boolean $case_sensitive Set to true to force 
* case sensitivity. Default: false (case insensitive). 
* @return string The longest string - first match. 
*/ 
function get_longest_common_subsequence($str1, $str2, $case_sensitive = false) { 
    // We'll use '#' as our regex delimiter. Any character can be used as we'll quote the string anyway, 
    $delimiter = '#'; 

    // We'll find the shortest string and use that to create our regex. 
    $l1 = strlen($str1); 
    $l2 = strlen($str2); 
    $str = $l1 <= $l2 ? $str1 : $str2; 
    $l = min($l1, $l2); 

    // Regex for each character will be of the format (?:a(?=b))? 
    // We also need to capture the last character, but this prevents us from matching strings with a single character. (?:.|c)? 
    $reg = $delimiter; 
    for ($i = 0; $i < $l; $i++) { 
     $a = preg_quote($str[ $i ], $delimiter); 
     $b = $i + 1 < $l ? preg_quote($str[ $i + 1 ], $delimiter) : false; 
     $reg .= sprintf($b !== false ? '(?:%s(?=%s))?' : '(?:.|%s)?', $a, $b); 
    } 
    $reg .= $delimiter; 
    if (! $case_sensitive) { 
     $reg .= 'i'; 
    } 
    // Resulting example regex from a string 'abbc': 
    // '#(?:a(?=b))?(?:b(?=b))?(?:b(?=c))?(?:.|c)?#i'; 

    // Perform our regex on the remaining string 
    $str = $l1 <= $l2 ? $str2 : $str1; 
    if (preg_match_all($reg, $str, $matches)) { 
     // $matches is an array with a single array with all the matches. 
     return array_reduce($matches[0], function($a, $b) { 
      $al = strlen($a); 
      $bl = strlen($b); 
      // Return the longest string, as long as it's not a single character. 
      return $al >= $bl || $bl <= 1 ? $a : $b; 
     }, ''); 
    } 

    // No match - Return an empty string. 
    return ''; 
} 

Se va a generar una expresión regular usando la más corta de las dos cadenas, aunque el rendimiento será muy probablemente el mismo en ambos sentidos. Puede coincidir incorrectamente cadenas con subcadenas recurrentes, y estamos limitados a cadenas coincidentes de dos caracteres o más. Por ejemplo:

// Works as intended. 
get_longest_common_subsequence('abbc', 'abc') === 'ab'; 

// Returns incorrect substring based on string length and recurring substrings. 
get_longest_common_subsequence('abbc', 'abcdef') === 'abc'; 

// Does not return any matches. 
get_longest_common_subsequence('abc', 'ace') === ''; 

Independientemente, funciona usando un método alternativo y la expresión regular puede ser refinado para hacer frente a situaciones adicionales.