Функция полиндром

[curva_nord]

Если создал тему не в том разделе прошу извинить. Помогите решить задачу:
Написать функцию поиска полиндрома максимальной длины в строке.
Пробовал сам,не получается =(
Я думаю так : необходимо сравнивать все символы начиная с крайних. $start - первый символ, $end - последний.
Сначала сравниваю первый символ с последним,если не одинаковы - с предпоследним и т.д.Если одинаковых не нашлось - берем второй символ и также сравниваем со всеми.Если символы равны - заносим его в новую строку,которую возвращает функция. Надеюсь на вашу помощь!

function palindrom ($str){

for($start=0;$start<strlen($str);$start++){
for ($end=strlen($str)-1;$end>=0;$end--){
if($str{$start}!==$str{$end} or $start==$end)
continue;
$str1{$start}=$str{$start};
}
}
return $str1;
}


echo palindrom('не пошл шопен');//Array

 

[rotoZOOM]

Если символы равны - заносим его в новую строку,которую возвращает функция.

Кого его? Совпавший символ? В какую строку?

P.S. очень напоминает на задачу на собеседовании.

Btw, в приведенном тобой примере максимальный палиндром будет единичной длины.

 

[curva_nord]

Кого его?

Да,совпавший символ

В какую строку?

в строку $str1,которую возвращает функция.
Уже все решил =D

function palindrom ( $str ) 
{ 
 $str1 = ''; 
 $str = preg_replace( "'\s'", '', strtolower( $str ) ); 

 for( $start = 0, $end = strlen( $str ) - 1; $start < $end; $start ++,$end-- ) 
 { 
 if ( $str{$start} !== $str{$end} ) 
break; 

 $str1 .= $str{$start}; 
 } 

 return $str1; 
}
echo palindrom('А роза упала на лапу Азора');//арозаупала

Вроде бы похожее на правду=)

 

[Вурдалак]

Ты рассмотрел самый тривиальный случай, когда твоя строка-палиндром будет симметрична относительно середины строки. Уже в строке «А роза упала на лапу Азора!» твоя функция ничего не найдёт.

Самый тупой алгоритм: перебор всех подстрок строки [O(n^2)] и проверка каждой подстроки на «палиндромность» [O(n)], т.е. алгоритм будет иметь сложность O(n^3). Плохо, но работать должно.

P.S. Проверку следует делать с более длинных подстрок, тогда при нахождении первого палиндрома работа функции завершается.

 

[rotoZOOM]

По-моему, гораздо проще перебрать каждый символ (или пару) O(n), считая это серединой палиндрома и "растекаться" в разные стороны O(n), в итоге получим O(n^2).

 

[Вурдалак]

Это тоже будет O(n^3).

В порядке вложенности:

1. Перебор каждого символа или пары символов.
2. Процесс «стекания» к этому символу или паре.
3. Проверка подстроки на «палиндромность».

По-моему, те же яйца.

 

[rotoZOOM]

$s = "mamapapapamma";
$max = 0;
$len = strlen($s);
for ($i = 0 ; $i < $len - 1 ; $i++)    /// O(n)
{
    /// проверка нечетной длины  O(n)
    for ($j = 0 ; $i - $j >=0 && $i + $j < $len && $s[$i - $j]==$s[$i + $j] ; $j++);
    $max = max($max,($j-1)*2+1);

    /// проверка четной длины  O(n)
    for ($j = 0 ; $i - $j >=0 && $i + 1 + $j < $len && $s[$i - $j]==$s[$i + 1 + $j] ; $j++);
    $max = max($max,$j*2);
}

Где тут O(n^3)? Может я чего не понимаю?
Итого O(n*(n+n)), а не O(n*n*n)

P.S. код не тестировал, но смысл понятен?

 

[Ragazzo]

rotoZOOM
дак у тебя же цикл в цикле, разве не O(n^2) ?

 

[rotoZOOM]

Ragazzo
Все верно, O(n^2), а не O(n^3)

 

[Вурдалак]

rotoZOOM, да, я ошибся, ты фактически объединил 2-й и 3-й пункты. Прикольно.

Но в силу того, что твой алгоритм только на «растекание» способен, что даже немного интересно: вдруг мой «тупой» будет даже побыстрее на небольших строках.

 

[rotoZOOM]

вдруг мой «тупой» будет даже побыстрее

В некоторых случаях я в этом уверен!
В любом случае, для ТС хоть O(n^5) подошел бы.

 

[curva_nord]

спасибо большое за помощь я только начал изучать php, поэтому нуждаюсь в практике. Если подкинете задач, буду признателен

 

[Ragazzo]

Как обычно гостевая книга

 

[curva_nord]

еще до этого не дошел...