ravi1989h Ответов: 1

Самый длинный палиндром в строке

Привет
можете ли вы сказать мне, как лучше всего найти самую длинную подстроку палиндрома в строке?
пожалуйста объяснить .я получил много ссылок, но не в состоянии понять

[no name]

Откуда нам знать, что именно вы не понимаете?

ravi1989h

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

Mike-MadBadger

Можете ли вы показать код, который вы нашли и который вы не можете следовать

Mike-MadBadger

Как вы уже сказали, существует множество источников информации.
Вы хотите сказать, что не понимаете код, который они используют?
Или что вы не до конца понимаете используемый язык (предполагая, что английский не является вашим родным языком)?

Очевидный подход, состоящий в том, чтобы взять каждую букву строки и работать от нее в обоих направлениях, кажется наименее эффективным (но он должен быть простым в программировании). Вам нужно найти "лучшие" ответы?

1 Ответов

Рейтинг:
2

OriginalGriff

Существует хороший разговор об этой проблеме, в комплекте с довольно оптимальным алгоритмом здесь:
http://www.akalin.cx/longest-palindrome-linear-time[^]
Он работает, ища палиндромы из центров, что является такой яркой идеей, что заставляет вас идти ":doh:! Почему я об этом не подумал?".

Я оставляю это как упражнение для читателя, чтобы реализовать его в C - но ему вообще не нужны никакие деревья!

JayantaChatterjee

Моя пятерка за алгоритм....

OriginalGriff

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

ravi1989h

отсюда я и нашел
http://stackoverflow.com/questions/7043778/longest-palindrome-in-a-string-using-suffix-tree

ravi1989h

проверить это

http://stackoverflow.com/questions/7043778/longest-palindrome-in-a-string-using-suffix-tree

ravi1989h

http://tristan-interview.blogspot.in/2011/11/longest-palindrome-substring-manachers.html

пожалуйста объясните на примере не в состоянии понять