Нахождение совпадающих частей двух строк в PHP

Question

Я ищу простой способ найти совпадающие части двух строк в PHP (в частности, в контексте URI)

Например, рассмотрим две строки:

http://2.2.2.2/~machinehost/deployment_folder/

и

/ ~ machinehost / deployment_folder / пользователей / боб / Настройки

Что мне нужно, так это отрезать совпадающую часть этих двух строк от второй строки, в результате чего:

Пользователи / боб / Настройка

перед добавлением первой строки в качестве префикса, формируя абсолютный URI.

Есть ли какой-нибудь простой способ (в PHP) сравнить две произвольные строки для сопоставления подстрок внутри них?

РЕДАКТИРОВАТЬ: как указывалось, я имел в виду самая длинная совпадающая подстрока, общая для обеих строк

Answer 1

Это будет ответом. Готовая к использованию функция PHP.

Answer 2

Предполагая, что ваши строки $a и $b, соответственно, вы можете использовать это:

$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;

Этот результат http://2.2.2.2/~machinehost/deployment_folder/users/bob/settings.

Answer 3

Найти самое длинное общее совпадение можно также с помощью регулярного выражения.

Следующая функция будет принимать две строки, использовать одну для создания регулярного выражения и выполнять ее в сравнении с другим.

/**
 * 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 ) {
    // First check to see if one string is the same as the other.
    if ( $str1 === $str2 ) return $str1;
    if ( ! $case_sensitive && strtolower( $str1 ) === strtolower( $str2 ) ) return $str1;

    // 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 check substrings and create our regex.
    $l1 = strlen( $str1 );
    $l2 = strlen( $str2 );
    $str = $l1 <= $l2 ? $str1 : $str2;
    $str2 = $l1 <= $l2 ? $str2 : $str1;
    $l = min( $l1, $l2 );

    // Next check to see if one string is a substring of the other.
    if ( $case_sensitive ) {
        if ( strpos( $str2, $str ) !== false ) {
            return $str;
        }
    }
    else {
        if ( stripos( $str2, $str ) !== false ) {
            return $str;
        }
    }

    // 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 '';
}

Он сгенерирует регулярное выражение, используя более короткую из двух строк, хотя производительность, скорее всего, будет одинаковой в любом случае.Он может некорректно сопоставлять строки с повторяющимися подстроками, и мы ограничены совпадением строк из двух или более символов, , если они не равны или одна из них не является подстрокой другой .Для экземпляра:

// 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, as all recurring strings are only a single character long.
get_longest_common_subsequence( 'abc', 'ace' ) === '';

// One of the strings is a substring of the other.
get_longest_common_subsequence( 'abc', 'a' ) === 'a';

Независимо от этого, он функционирует с использованием альтернативного метода, и регулярное выражение может быть уточнено для решения дополнительных ситуаций.

Answer 4

это не похоже на готовый код для вашего требования.Итак, давайте посмотрим на простой способ.

В этом упражнении я использовал два метода, один для нахождения самого длинного совпадения, а другой - для отрезания совпадающей части.

FindLongestMatch() метод, разбирает путь, кусок за куском ищет совпадение на другом пути, сохраняя только одно совпадение, самое длинное (без массивов, без сортировки).Метод RemoveLongestMatch () принимает суффикс или «остаток» после самой длинной найденной позиции соответствия.

Здесь полный исходный код:

<?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;
}

Это представительПодмножество тестовых случаев:

//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);

Запуск предыдущих тестовых примеров дает следующий вывод:

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

Может быть, вы можете взять идею этого куска кода и превратить его в нечто, что вынайти полезным для вашего текущего проекта.Дайте мне знать, если это сработало и для вас.Кстати, и мистер oreX тоже неплохо выглядит.

Answer 5

Попробуйте это.

http://pastebin.com/GqS3UiPD

Answer 6

Я не уверен, что понимаю ваш полный запрос, но идея такова:

Пусть A будет вашим URL, а B - вашим "/ ~ machinehost / deploy_folder / users / bob / settings"

• поиск B в A -> вы получите индекс i (где i - позиция первого / из B в A)
• пусть l = длина (A)
• Вам нужно сократить B от (l-i) до длины (B), чтобы получить последнюю часть B (/ users / bob / settings)

Я еще не тестировал, но если вам действительно нужно, я могу помочь вам заставить это блестящее (ироничное) решение работать.

Обратите внимание, что это возможно при использовании регулярных выражений, таких как

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

Редактировать: Я думаю, что ваш последний комментарий лишает законной силы мой ответ. Но вы хотите найти подстроки. Поэтому вы можете сначала начать с тяжелого алгоритма, пытаясь найти B [1: i] в A для i в {2, length (B)}, а затем использовать динамическое программирование вещи.