$a = «Hello, my name is Anna» $b="Hello, my name is Kevin" как сравнивать a и b, и узнать есть ли совпадение 5 букв по последовательности?

Question

[Lavrov95]

$a = "Hello, my name is Anna" $b="Hello, my name is Kevin" как сравнивать a и b, и узнать есть ли совпадение 5 букв по последовательности?

Comments

[devalone]

Уточните задачу, последовательности должны начинаться с одного и того же символа в обоих строках, т.е. так:

фываывф 5символов фываыфва
234123435символов2354ваыва

или могут с разных, т.е.

5символовфываывф фываыфва
234123435символов2354ваыва

?

[BoShurik]

Какая изначально задача стоит? Может быть подойдет расстояние Левенштейна?

$a = 'Hello, my name is Anna';
$b = 'Hello, my name is Kevin';

echo levenshtein($a, $b) . "\n"; // 5

Answer 1

[Павел Гоголинский]

Как вариант
1. Сформировать массив всех возможных пятибуквенных последовательностей из первой строки
2. Такой же массив из второй строки
3. Найти, есть ли схождение (array_intersect)

Comments

[devalone]

Зачем делать лишние массивы?

[Дядька Серёжа]

devalone, критикуя предлагай

[devalone]

Дядька Серёжа, перебираем в цикле элементы первой строки(до length - 5), в него вложен цикл, где перебираются элементы второй строки, в нём проверка на равенство символов, если равно проверяем следующие 4 и возвращаем true, если же символ в подпоследовательности отличается, то продолжаем искать дальше, если не нашли, возвращаем false. Но это одно из возможных решение, пускай ТС уточнит задачу, может ему нужно искать не все возможные, а только те, которые на одинаковых индексах.

Answer 2

[artem78]

Поиск общей последовательности в двух строках: https://en.wikibooks.org/wiki/Algorithm_Implementa...

Answer 3

[xmoonlight]

1. Узнать: сколько бит содержится в каждом символе, составив строку-маску цепочек нулевых и единичных битов, каждая цепочка - это один символ.
2. Выполнить $a XOR $b и посчитать кол-во 0-х битов, идущих подряд (во всех цепочках последовательностей).
3. Как только >=5 символов - значит мы нашли искомую последовательность.

Comments

[devalone]

Так может ТС имел ввиду такое?
"It's test string 1"
"another test str"
Т.е. общие подпоследовательности в 5 символов есть, но не обязательно начинаются с того же индекса

[devalone]

1. Узнать: сколько бит содержится в одном символе, исходя из кодировки.

и да, как вы будете узнавать в UTF8?

[xmoonlight]

devalone, может... я сделал максимально быстро по предложенному примеру.

[devalone]

А ещё у меня сомнения, что оно будет в среднем работать быстрее такого алгоритма:
1 перебираем символы первой и второй строки
2 если символы одинаковые, инкрементируем счётчик, если разные - сбрасываем в ноль
3 если счётчик >= 5, возвращаем true
4 если перебрали всё и счётчик < 5, возвращаем false
т.к. у вас делается XOR для всей строки, а здесь же, если последовательность вначале, остальная часть даже не проверяется.

[xmoonlight]

devalone, мда... неувязочка) признаю! Надо, значит, вначале получить массив по длине кодировки каждого символа в битах.

[xmoonlight]

devalone, ну т.е. по аналогии, как я делал для fuzzy substring: gist? да?
Я не думаю, что будет быстрее, чем два раза XOR сделать. Но при условии, что индекс - одинаковый...
А про сдвинутые - "скользящее окно" через бинарный сдвиг, а вот кол-во символов как считать - это вопрос)