Warning: Cannot use a scalar value as an array in /home/admin/public_html/forum/include/fm.class.php on line 757

Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/include/fm.class.php on line 770

Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/topic.php on line 737
Форумы портала PHP.SU :: Поиск самой длинной подстроки в строке

 PHP.SU

Программирование на PHP, MySQL и другие веб-технологии
PHP.SU Портал     На главную страницу форума Главная     Помощь Помощь     Поиск Поиск     Поиск Яндекс Поиск Яндекс     Вакансии  Пользователи Пользователи


 Страниц (1): [1]   

> Без описания
Striker
Отправлено: 15 Июля, 2015 - 23:18:58
Post Id



Частый гость


Покинул форум
Сообщений всего: 128
Дата рег-ции: Июль 2011  
Откуда: Киев


Помог: 1 раз(а)

[+]


Например есть рамдомная строка:

$string = 'AfdfgggdhrFFFFFjkko';

Самая длинная подстрока из одинаковых символов здесь "FFFFF", каким алгоритмом ее можно вычислить?
 
 Top
Tyoma5891
Отправлено: 16 Июля, 2015 - 08:52:54
Post Id


Частый посетитель


Покинул форум
Сообщений всего: 621
Дата рег-ции: Авг. 2013  


Помог: 5 раз(а)




Striker пишет:
Например есть рамдомная строка:

$string = 'AfdfgggdhrFFFFFjkko';

Самая длинная подстрока из одинаковых символов здесь "FFFFF", каким алгоритмом ее можно вычислить?

самый тупой в лоб вариант это находить подстроки с одинаковыми символами подряд вплоть до регистра а потом вычислять и сравнивать их длины
 
 Top
Tyoma5891
Отправлено: 16 Июля, 2015 - 11:59:00
Post Id


Частый посетитель


Покинул форум
Сообщений всего: 621
Дата рег-ции: Авг. 2013  


Помог: 5 раз(а)




половина решения Вашей задачи вот:
PHP:
скопировать код в буфер обмена
  1. $string = 'AfdfgggdhrFFFFFjkktttttttto';
  2. preg_match_all("#(.)\\1{1,}#",$string, $matches);

дальше сами, надеюсь)

(Отредактировано автором: 16 Июля, 2015 - 11:59:45)

 
 Top
Striker
Отправлено: 16 Июля, 2015 - 12:25:47
Post Id



Частый гость


Покинул форум
Сообщений всего: 128
Дата рег-ции: Июль 2011  
Откуда: Киев


Помог: 1 раз(а)

[+]


Tyoma5891 пишет:
половина решения Вашей задачи вот:
PHP:
скопировать код в буфер обмена
  1. $string = 'AfdfgggdhrFFFFFjkktttttttto';
  2. preg_match_all("#(.)\\1{1,}#",$string, $matches);

дальше сами, надеюсь)

Спасибо! А вариант без регулярок?
 
 Top
Tyoma5891
Отправлено: 16 Июля, 2015 - 12:32:16
Post Id


Частый посетитель


Покинул форум
Сообщений всего: 621
Дата рег-ции: Авг. 2013  


Помог: 5 раз(а)




Striker пишет:
А вариант без регулярок?

мне лично в голову больше ничего не приходит как посимвольный перебор в цикле все строки и вынимая из нее символы идущие подряд одинаковые, но кода будет поболее нежели в случае с регуляркой...
(Добавление)
Tyoma5891 пишет:
Striker пишет:
А вариант без регулярок?

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

зы вообще может пересмотреть все функции для строк может там что еще найдется алтернативное...
 
 Top
esterio
Отправлено: 16 Июля, 2015 - 12:50:11
Post Id



Активный участник


Покинул форум
Сообщений всего: 5025
Дата рег-ции: Нояб. 2012  
Откуда: Украина, Львов


Помог: 127 раз(а)




 
 Top
Tyoma5891
Отправлено: 16 Июля, 2015 - 12:55:12
Post Id


Частый посетитель


Покинул форум
Сообщений всего: 621
Дата рег-ции: Авг. 2013  


Помог: 5 раз(а)




esterio пишет:

как она в этой задаче может помочь?
 
 Top
esterio
Отправлено: 16 Июля, 2015 - 13:27:10
Post Id



Активный участник


Покинул форум
Сообщений всего: 5025
Дата рег-ции: Нояб. 2012  
Откуда: Украина, Львов


Помог: 127 раз(а)




Tyoma5891
И правда не заметил что из одной букв
 
 Top
DeepVarvar Супермодератор
Отправлено: 16 Июля, 2015 - 14:25:47
Post Id



Активный участник


Покинул форум
Сообщений всего: 10377
Дата рег-ции: Дек. 2008  
Откуда: Альфа Центавра


Помог: 353 раз(а)




Striker пишет:
Самая длинная подстрока из одинаковых символов
А например тут они все одинаково самые длинные:

ABCDEFG

или тут:

AABBCCDDEEFFGG

Какую из подстрок в таком случае считать сАмой-сАмой из самых и почему?
 
 Top
Striker
Отправлено: 16 Июля, 2015 - 14:33:10
Post Id



Частый гость


Покинул форум
Сообщений всего: 128
Дата рег-ции: Июль 2011  
Откуда: Киев


Помог: 1 раз(а)

[+]


Вот один из вариантов решений, друг подсказал:

CODE (htmlphp):
скопировать код в буфер обмена
  1. $string = 'AfdfggggggggggggdhrFFFFFjkko';
  2.  
  3. $lastSym = null;
  4. $maxSym = null;
  5. $maxLen = 1;
  6. $curLen = 1;
  7.  
  8. for ($i = 0, $len = strlen($string); $i < $len; $i++)
  9. {
  10.         $curSym = $string[$i];
  11.  
  12.         if(!$maxSym)
  13.         {
  14.                 $maxSym = $curSym;
  15.         }
  16.  
  17.         if($curSym === $lastSym)
  18.         {
  19.                 if(++$curLen > $maxLen)
  20.                 {
  21.                         $maxSym = $curSym;
  22.                         $maxLen = $curLen;
  23.                 }
  24.         } else {
  25.                 $curLen = 1;
  26.         }
  27.  
  28.         $lastSym = $curSym;
  29. }
  30.  
  31. $result = str_repeat($maxSym, $maxLen);
  32.  
  33. echo $result;


Это задание на одном из собеседований. Его надо было сделать на листке бумаги, без какой-либо помощи (без гугла), за 20 мин. Собеседование я завалил, насчет задания просто интересно стало как это реализовать.
 
 Top
DeepVarvar Супермодератор
Отправлено: 16 Июля, 2015 - 14:38:11
Post Id



Активный участник


Покинул форум
Сообщений всего: 10377
Дата рег-ции: Дек. 2008  
Откуда: Альфа Центавра


Помог: 353 раз(а)




Плевать откуда это идиотское задание.
Ты на мой вопрос то ответь.
(Добавление)
И код, который ты привел как решение -- зафейлится на том о чем я уточняю и на многобайтных кодировках.
(Добавление)
И по PSR стандартам у форов-ифов-эльзов кучерявая скобка не переносится на новую строку, а инденты делаются в 4 пробела, а не табом.
 
 Top
Striker
Отправлено: 16 Июля, 2015 - 14:41:54
Post Id



Частый гость


Покинул форум
Сообщений всего: 128
Дата рег-ции: Июль 2011  
Откуда: Киев


Помог: 1 раз(а)

[+]


DeepVarvar
Цитата:
А например тут они все одинаково самые длинные:

ABCDEFG

А ты даже не понял задание. Забей.

Про много байтовые кодировки не было и речи, только англ буквы.
 
 Top
DeepVarvar Супермодератор
Отправлено: 16 Июля, 2015 - 14:45:14
Post Id



Активный участник


Покинул форум
Сообщений всего: 10377
Дата рег-ции: Дек. 2008  
Откуда: Альфа Центавра


Помог: 353 раз(а)




Я таки это задание понял даже глубже чем многие.
Но ты забей, всеравно уже поздно ))
(Добавление)
Striker пишет:
Про много байтовые кодировки не было и речи
Striker пишет:
Например есть рамдомная строка:

$string = 'AfdfgggdhrFFFFFjkko';
Например! Рандомная! Значит многобайтные тоже туда входят.
Striker пишет:
подстрока
Разве она не может состоять из одного символа?
 
 Top
Striker
Отправлено: 16 Июля, 2015 - 14:50:26
Post Id



Частый гость


Покинул форум
Сообщений всего: 128
Дата рег-ции: Июль 2011  
Откуда: Киев


Помог: 1 раз(а)

[+]


DeepVarvar
Не придирайся. Общая суть понятна всем понятна. Если до тебя сразу не дошло - мог бы не отвечать. Я не собираюсь тут расписывать задание на две страницы А4, учитывая все моменты, ибо его никто даже не прочитает. Разговор окончен.

(Отредактировано автором: 16 Июля, 2015 - 14:51:18)

 
 Top
DeepVarvar Супермодератор
Отправлено: 16 Июля, 2015 - 14:53:56
Post Id



Активный участник


Покинул форум
Сообщений всего: 10377
Дата рег-ции: Дек. 2008  
Откуда: Альфа Центавра


Помог: 353 раз(а)




А я не об этом.
Я о том что ты сам на собеседовании мог бы устроить "кузькину мать" мягко докопавшись до задающего с этими нюансами.
В любом случае тебе бы это сыграло в плюс.
(Добавление)
Striker пишет:
Общая суть понятна всем
В алгоритмах и условиях суть не может быть общей, она там одна и единственная.
Все остальное -- говнокод.
 
 Top
Страниц (1): [1]
Сейчас эту тему просматривают: 0 (гостей: 0, зарегистрированных: 0)
« Напишите за меня, пожалуйста »


Все гости форума могут просматривать этот раздел.
Только зарегистрированные пользователи могут создавать новые темы в этом разделе.
Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.
 



Powered by PHP  Powered By MySQL  Powered by Nginx  Valid CSS  RSS

 
Powered by ExBB FM 1.0 RC1. InvisionExBB