Как найти уникальные последовательности символов в двух строках?

Здравствуйте, необходима помощь в составлении алгоритма или поиске готового варианта. Я хочу создать скрипт, который сравнивает две или более строки и находит только уникальные последовательности в каждой строке.


Например:
www.youtube.com/user/grickle#p/u/0/tuhZuMl9StM
www.youtube.com/user/grickle#p/u/3/hnvkIQHv0OQ
www.youtube.com/user/grickle#p/u/7/cjT2Huux34g
www.youtube.com/user/grickle#p/u/2/Osex3fXi_OA


Заранее спасибо за помощь!
  • Вопрос задан
  • 7044 просмотра
Пригласить эксперта
Ответы на вопрос 8
m08pvv
@m08pvv
Может проще найти максимальную совпадающую подстроку?
Ответ написан
@yopopt
Набросал на javascript свой вариант конкретно для случая с подобными строками. Быть может пригодится.
  1. /**
  2. * strings - массив исходных строк
  3. * result - массив уникальные последовательности символов
  4. */
  5. var strings = [
  6.   'www.youtube.com/user/grickle#p/u/dasdas/0/tuhZuMl9StM',
  7.   'www.youtube.com/user/grickle#p/u/dasd as/3/hnvkIQHv0OQ',
  8.   'www.youtube.com/user/grickle#p/u/vcx bxcv/7/cjT2Huux34g',
  9.   'www.youtube.com/user/grickle#p/u/54354/2/Osex3fXi_OA'
  10.   ],
  11.   temp = [],
  12.   result = [],
  13.   repeat = {},
  14.   newStrings = {};
  15.   
  16.   /**
  17.    * Обходим исходный массив и разбиваем его по повторяющимся символам,
  18.    * здесь это слеши. Создаём объект с ключами из уникальных строк, а
  19.    * значения - индексы этих строк в разделённой оригинальной строке.
  20.    * одинаковые же части сохраняем в массив повторяющихся.
  21.    */
  22.   for(var i = 0; i<strings.length; i++) {
  23.     temp[i] = strings[i].split('/');
  24.     result[i] = '';
  25.     for(var j = 0; j<temp[i].length; j++) {
  26.       if(temp[i][j] in newStrings) {
  27.         repeat[temp[i][j]] = 1;
  28.       }
  29.       newStrings[temp[i][j]] = i;
  30.     }
  31.   }
  32.   
  33.   /**
  34.    * Склеиваем уникальные части строки в одну.
  35.    */
  36.   for(var key in newStrings) {
  37.     if(!(key in repeat))
  38.      result[newStrings[key]]+=(result[newStrings[key]]!=''?'/':'')+key;
  39.   }
Ответ написан
Комментировать
Кстати, в приведённых примерах будут две строки. Например, для первой «0» и «tuhZuMl9StM».

А вот моё неоптимальное решение «в лоб».
$strs[] = 'www.youtube.com/user/grickle#p/u/0/tuhZuMl9StM';
$strs[] = 'www.youtube.com/user/grickle#p/u/3/hnvkIQHv0OQ';
$strs[] = 'www.youtube.com/user/grickle#p/u/7/cjT2Huux34g';
$strs[] = 'www.youtube.com/user/grickle#p/u/2/Osex3fXi_OA';
$return = array();

foreach ($strs as $key => $str1)
    {
    $return[$key] = array();
    foreach($strs as $str2)
        {
        $astr1 = str_split($str1);
        $astr2 = str_split($str2);
        $array_diff = array_diff_assoc($astr1, $astr2);
        $return[$key] = $return[$key] + $array_diff;
        }
    ksort($return);
    }
var_dump($return);


В результате получится массив символов, где индексы — это их позиция. Можете получить из них одну строку, несколько строк или работать с массивами так как есть — это уже не важно.
Ответ написан
Комментировать
Если массив ссылок хранится в файле, то товарищи выше уже дали варианты.
Могу предположить, что сборка ссылок хранится в БД. Тогда, в случае MySQL выборка уникальный значений в столбце | (столбце + строке) будет находиться стандартным запросом SELECT DISTINCT `column` FROM `database.table` LIMIT `max_rows`;
Ответ написан
Комментировать
sort(row);
row = "";
while (row_next)
{
if( row == row_next) // your condition
{
print('blbeleblbele');
...
}
row = row_next;
}
Ответ написан
nalomenko
@nalomenko
Руководитель отдела разработок в студии «Lava»
Можно попробовать библиотеки, используемые в diff'e, который сравнивает разные версии файлов на предмет отличий.
Ответ написан
taliban
@taliban
php программист
Есть вариант в лоб, для ленивых:
есть два цикла, первый проходит по первой строке, второй по второй
на каждую итерацию первого цикла нужно проверять вторую строку с начала
при совпадении символов, второй цикл начинается с позиции равной количеству совпаденных символов
наиболее длинное совпадение сохраняем и заменяем ранее сохраненное, если оно есть
!!!
PROFIT

если кто не понял
abcd
cd
a=c — no
b=c — no
c=c — yes
d=d — yes
max = cd

Это тупейший поиск похожих вхождений, как найти разницу думаю не составит труда =)
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы