@amatoriste

Найти в строке подстроку, которая содержит максимальное количество последовательных символов в этой строке?

К примеру.
Есть строка
$str= 'abcccdefghijklm234nnnnopqqrerrstuvwxyz0156789';

Нужно получить из неё подстроку, с максимальным количеством последовательных символов .

Есть идея:
сделать через preg_split() , найти уникальные подстроки и потом пройти по массиву и найти строку с макс. длинной.
Но я застопорился с самой регуляркой.
Не могу раздуплиться как правильно записать последовательность без повторений.
Может есть Добрый Человек который может подсказать?))
  • Вопрос задан
  • 450 просмотров
Пригласить эксперта
Ответы на вопрос 3
sergiks
@sergiks Куратор тега PHP
♬♬
Надо двигать концы отрезка: правый R и левый L. Изначально оба на нуле.
Держим текущий набор символов, чтобы проверять на повторы. Помним найденный максимальный отрезок.
Двигаем правый конец на 1. Если символа нет в наборе, добавляем. Если есть, двигаем L вправо за найденный символ. Перед этим проверяем, а не нашли ли мы очередной максимум.

Очень кривая спать-хочу реализация, вроде, работает: Ideone

Старый ответ, please ignore: Двигаться по одному символу. Помнить найденную макс. длину. Сравнивать символ с предыдущим.
Равен – длина текущего сегмента растёт.
Не равен – закончился предыдущий сегмент и начался новый. Если длина больше найденного максимума – найден очередной кандидат. Запомнить его длину и начало. Запомнить начало очередного сегмента и считать длину с 1.

Итого один раз пройтись. Не надо регулярок.
Ответ написан
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Никого не слушайте: Это Хаффман.
Ответ написан
Immortal_pony
@Immortal_pony Куратор тега PHP
function findTheLongestSequence($str) {
    $sequences = [];
    $sequence = "";
    
    for ($letterIndex=0; $letterIndex<strlen($str); $letterIndex++) {
        $letter = $str[$letterIndex];
        $previousLetterIndex = ($letterIndex-1);
        $previousLetter = (isset($str[$previousLetterIndex]) ? $str[$previousLetterIndex] : null);

        if ($previousLetter === $letter) {
            if (!empty($sequence)) {
                $sequences[] = $sequence;
                $sequence = "";
            }
        } else {
            $sequence .= $letter;
        }
        
        if (strlen($str)-1 === $letterIndex && !empty($sequence)) {
            $sequences[] = $sequence;
        }
    }
    
    usort($sequences, function($someSequence, $otherSequence) {
        return strlen($otherSequence)-strlen($someSequence);
    });
    
    return $sequences[0];
}


PS Если программист начинает решать проблему с помощью регулярного выражения, то у него появляется две проблемы(с).
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы