Всем добрый вечер, кому то добрый день, а кому то возможно и утро) Я застрял на задаче. Есть массив. Допустим ["волк","волейбол","восток"] Далее в чем же суть задачи? Нужно найти у слов данного массива общую часть в данном случае это "во". Звучит то просто, а вот на деле уже часа 2 сижу и мыслей ноль. Перебирать каждую букву как вариант, но реализацию этого тоже сложно сделать, что если общая часть у одного слова начинается с начала слова а у второго с конца или в центре. Накидайте идей))
Берём самое короткое слово в массиве Из него формируем перебором всевозможные части, типа первый символ с 0 позиции, два символа итд, потом переходим к 1 позиции где точно так же, цикл в цикле... Каждое полученное сочетание проверяем на вхождени во всё слова массива
1) Нашел минимальную строку в массиве, если несколько одинаковых, берем любую. 2) Не забыл установить php_mbstring.dll, чтобы работать с русским текстом (кому я вру?) 3) Решил найти все возможные шаблоны для регулярок из той самой строки с 1-го пункта. 4) Для создания шаблонов иду от всех символов по убыванию, заменяя символы на ".*". Хочу для этого использовать substr_replace (), но для работы с русским текстом нету mb_substr_replace() - значит пишу такую функцию (гуглю в инете). Вспоминаю как делать рекурсию. 5) Не забываю добавить в массив с шаблонами строку из 1-го пункта (почему-то делаю это вне функции (потому что криворук)). 6) Чищу массив с шаблонами от дубликатов и 1-го мусорного шаблона. Как он там оказался? (смотри комментарий пункта 5). 7) Использую все шаблоны в регулярках, там нахожу по всем строкам из начального условия совпадения и кидаю эти шаблоны в отдельный массив. 8) Нахожу шаблоны, в которых у меня меньше всего ".*", а значит там самое длинное совпадение. Вывожу этот массив. Для интереса к "волейбол" добавил в конце символ "к". Собственно вот мое чудовище, но зато работает (пока лень полировать, и вообще готовое решение для слабых): PHP: <?php $having_arr = ["волк", "волейболк", "восток"]; if (!function_exists('mb_substr_replace')) { function mb_substr_replace($original, $replacement, $position, $length) { $startString = mb_substr($original, 0, $position, 'UTF-8'); $endString = mb_substr($original, $position + $length, mb_strlen($original), 'UTF-8'); $out = $startString . $replacement . $endString; return $out; } } function get_min_str_in_arr($arr) { $str = $arr["0"]; for ($i = count($arr) - 1; $i > 0; $i--) { if (!is_string($arr[$i])) { continue; }; if (mb_strlen($arr[$i]) <= mb_strlen($str)) { $str = $arr[$i]; }; }; return $str; }; function find_math($pattern, $str) { return preg_match("/$pattern/iu", $str); }; function is_math_all($maths_arr) { $boolean = 1; for ($i = 0; $i < count($maths_arr); $i++) { $boolean = $boolean * $maths_arr[$i]; } return $boolean; } function get_all_pattern($str, $patterns_arr) { if ($str == ".*.*.*.*") { return $patterns_arr; } for ($i = mb_strlen($str) - 1; $i >= 0; $i--) { if (mb_substr($str, $i, 1, "UTF-8") == "." || mb_substr($str, $i, 1, "UTF-8") == "*") { continue; } $replaced_str = mb_substr_replace($str, ".*", $i, 1); array_push($patterns_arr, $replaced_str); $patterns_arr = get_all_pattern($replaced_str, $patterns_arr); } return get_all_pattern($replaced_str, $patterns_arr); } function clean_pattern($arr) { $arr = array_unique($arr); $cleaned_arr = []; $i = 0; foreach ($arr as $key => $value) { //Удаляю плохой шаблон для регулярки, лень доводить до ума, чтобы она туда не попадала. if ($value == ".*.*.*.*") { unset($arr[$key]); $i++; continue; } $cleaned_arr[$i] = $arr[$key]; $i++; } return $cleaned_arr; } function find($having_arr, $patterns_arr) { $almost_end = []; foreach ($patterns_arr as $pattern) { $maths_arr = []; foreach ($having_arr as $key => $having_str) { array_push($maths_arr, find_math($pattern, $having_str)); }; if (is_math_all($maths_arr)) { array_push($almost_end, $pattern); } } return $almost_end; } function end_this($arr) { $end_arr = []; $nubmer_arr = []; foreach ($arr as $key => $value) { $new_value = preg_match_all("/\.\*/", $value); array_push($nubmer_arr, $new_value); } $min = min($nubmer_arr); foreach ($arr as $key => $value) { if (preg_match_all("/\.\*/", $value) == $min) { array_push($end_arr, $value); } } return $end_arr; } $min_str = get_min_str_in_arr($having_arr); $patterns_arr = get_all_pattern($min_str, $patterns_arr = []); array_unshift($patterns_arr, $min_str); $patterns_arr = clean_pattern($patterns_arr); $almost_end_arr = find($having_arr, $patterns_arr); var_dump(end_this($almost_end_arr));
Причесал: PHP: <?php $having_arr = ["волк", "волейболк", "восток"]; if (!function_exists('mb_substr_replace')) { function mb_substr_replace($original, $replacement, $position, $length) { $startString = mb_substr($original, 0, $position, 'UTF-8'); $endString = mb_substr($original, $position + $length, mb_strlen($original), 'UTF-8'); $out = $startString . $replacement . $endString; return $out; } } function get_min_str_in_arr($arr) { $str = $arr["0"]; for ($i = count($arr) - 1; $i > 0; $i--) { if (mb_strlen($arr[$i]) <= mb_strlen($str)) { $str = $arr[$i]; }; }; return $str; }; function get_all_pattern($str, $patterns_arr, $max_str_replaced) { if (preg_match_all("/\.\*/iu", $str) == $max_str_replaced) { return $patterns_arr; } for ($i = mb_strlen($str) - 1; $i >= 0; $i--) { if (mb_substr($str, $i, 1, "UTF-8") == "." || mb_substr($str, $i, 1, "UTF-8") == "*") { continue; } $replaced_str = mb_substr_replace($str, ".*", $i, 1); array_push($patterns_arr, $replaced_str); $patterns_arr = get_all_pattern($replaced_str, $patterns_arr, $max_str_replaced); } return get_all_pattern($replaced_str, $patterns_arr, $max_str_replaced); } function clean_pattern($arr) { $arr = array_unique($arr); //Rename key after deleting doubles $cleaned_arr = []; $i = 0; foreach ($arr as $key => $value) { $cleaned_arr[$i] = $arr[$key]; $i++; } return $cleaned_arr; } function find_math($pattern, $str) { return preg_match("/$pattern/iu", $str); }; function is_math_all($maths_arr) { $boolean = 1; for ($i = 0; $i < count($maths_arr); $i++) { $boolean = $boolean * $maths_arr[$i]; } return $boolean; } function find_the_same($having_arr, $patterns_arr) { $almost_end = []; foreach ($patterns_arr as $pattern) { $maths_arr_boolean = []; foreach ($having_arr as $key => $having_str) { array_push($maths_arr_boolean, find_math($pattern, $having_str)); }; if (is_math_all($maths_arr_boolean)) { array_push($almost_end, $pattern); } } return $almost_end; } function end_this($arr) { $end_arr = []; $nubmer_arr = []; foreach ($arr as $key => $value) { $new_value = preg_match_all("/\.\*/iu", $value); array_push($nubmer_arr, $new_value); } $min = min($nubmer_arr); foreach ($arr as $key => $value) { if (preg_match_all("/\.\*/iu", $value) == $min) { array_push($end_arr, $value); } } return $end_arr; } $min_str = get_min_str_in_arr($having_arr); $max_str_replaced = mb_strlen($min_str) - 1; $patterns_arr = get_all_pattern($min_str, $patterns_arr = [], $max_str_replaced); array_push($patterns_arr, $min_str); $patterns_arr = clean_pattern($patterns_arr); $almost_end_arr = find_the_same($having_arr, $patterns_arr); var_dump(end_this($almost_end_arr));
Мой вариант решения задачи. https://php.ru/forum/threads/algoritmy-poleznosti.54173/page-2#post-660404
Тут поиск общих символов только подряд. Решение красивое. Я так понимаю, поиск по ключам происходит намного быстрее? Через глобальную переменную моя рекурсия простая и понятная становится: PHP: function get_all_pattern($str, $max_str_replaced) { if (preg_match_all("/\.\*/iu", $str) == $max_str_replaced) { return; } for ($i = mb_strlen($str) - 1; $i >= 0; $i--) { if (mb_substr($str, $i, 1, "UTF-8") == "." || mb_substr($str, $i, 1, "UTF-8") == "*") { continue; } $replaced_str = mb_substr_replace($str, ".*", $i, 1); array_push($GLOBALS["patterns_arr"], $replaced_str); get_all_pattern($replaced_str, $max_str_replaced); } } $max_str_replaced = mb_strlen($min_str) - 1; $patterns_arr = []; get_all_pattern($min_str, $max_str_replaced);