Подскажите пожалуйста алгоритм нахождения полиндромов.Желательно самый эффективный.Мож у кого и исходник завалялся, тож не откажусь
.Заранее спасибо.
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Алгоритм нахождения полиндромов |
| Автор: Psyhonaut 19.4.2006, 00:33 |
| Поискал поиском по форуму, нашлось пару тем, но в них идет обсуждение что такое полиндромы и т.д.Но самого алгоритма не нашлось. Подскажите пожалуйста алгоритм нахождения полиндромов.Желательно самый эффективный.Мож у кого и исходник завалялся, тож не откажусь .Заранее спасибо. |
| Автор: maxim1000 19.4.2006, 00:57 | ||
пример на C++
подходит? если нет, то неплохо было бы описать нахождение каких именно палиндромов нужно или, может быть, всех? тогда перебирать все строки и делать из них палиндромы... |
| Автор: SoWa 19.4.2006, 04:43 |
| Палиндром находится перебором. И в зависимости от длинны текста(чет нечет). Прочто с двух краев идешь по буквам слова, и если встретились неодинаковые- берешь другое слово. Задача интереснее, когда в тексте найти самый длинный палиндром. |
| Автор: chaos 19.4.2006, 06:16 | ||
а че тут интереснее то  |
| Автор: Akina 19.4.2006, 08:52 |
| if str == strreverse(str) {cout << str;} |
| Автор: Psyhonaut 20.4.2006, 20:32 |
| В программу передается текст.Необходимо найти все полиндромы.Просто задачку задали по предмету комбинаторные алгоритмы, вот и думаю, мож существует какой хитрый комбинаторный алгоритм.Идея сравнивать буквы по краям возникала. Как эффективнее хранить слово?Просто можно создать заведомо большой массив, и запоминать, при считывании длину слова, чтоб знать с какого элемента в конце сравнивать.Или есть более эффективный способ? |
| Автор: maxim1000 20.4.2006, 22:24 |
| ну тогда можно например так: перебираем по очереди все символы строки (кроме первого и последнего) и проверяем, являются ли они центрами палиндромов и, если да, то каких от каждого символа растягиваем отрезок в обе стороны, пока буквы по краям одинаковые на каждом шаге выводим содержимое отрезка это даст все палиндромы с нечетной длиной для получения палиндромов с четной длиной ищем в строке те места, в которых два одинаковых символа стоят друг рядом с другом и делаем для них то же, что и для одного символа пример: строка: qweretteq 1. для получения нечетных палиндромов: первый пропускаем, берем w добавляем соседние символы: qwe, т.к. символы по краям разные - забываем про w для e - то же самое берем r, добавляем соседей: ere, символы по краям одинаковые - выводим, добавляем еще соседей: weret, символы по краям разные - прекращаем проверяем остальные символы - здесь больше палиндромов с нечетной длиной нету 2. для получения четных палиндромов: ищем i: s[i]=s[i+1] находим tt, выводим добавляем соседей: ette символы по краям одинаковые - выводим добавляем соседей: retteq символы разные прекращаем... |
| Автор: nostromo 21.4.2006, 08:36 |
| То Psyhonaut: "Ваш способ меня не устраивает, он слишком простой." Чем предложение Akina то не подходит? И к чему вопрос как эффективнее хранить слово, std::string недостаточно эффективен? Бешеные требования к производительности? |
| Автор: Psyhonaut 17.5.2006, 05:27 | ||
Преподователь просто такой(одна из его фраз - "Олимпиадники(имеется ввиду участники мирового чемпионата по програмированию) делают такую задачу за два цикла, вы мне за один напишите"). Начал я писать програмку, пока что только для слов с четным количеством букв написал.Но есть какие то странные баги.Когда ее запускаю, выдает ошибку I/O. Прошелся я по строчкам, проследил процесс выполнения, вот что обнаружил.Массив для хранения слова - 10 элементов. Начинаю считывать слово(просто для примера, взал слово из 4 букв, после слова стоит запятая).Считывает все 4 буквы, потом считывает запятую, после этого он по идее должен идти на проверку слова(полиндром ли?), так как обнаружен разделитель(запятая), но прога продолжает считывать символы.После запятой пустота, т.е. должен закончится цикл, так как он задан так while (символ <> EoF), но продолжает считывать в массив символ с кодом 26.Причем считывает пока не накидает в массив 18 элементов(хотя размерность массива 10  ), потом программа завершается с ошибкой.В чем проблема, помогите пожалуйста. Во вложении программа.Только что копался в ней, пытался исправить, мож чего намудрил, так как рубит уже страшно. Заранее спасибо за помощь. |
| Автор: Mayk 17.5.2006, 06:06 |
| для текста длины n можно за O(n*log(n)): 0) Пробегаемся по всему тексту и запоминаем где какая буква стояла в разные массивы [любые контейнеры, в которое возможно добавление за О(1) и бинарный поиск за O(log2(N)) ]. Далее для каждой буквы исходного текста A: (пусть cur - текущая буква) 1) использую массивы из 0) находим бинарным поиском где в A стоит следующая буква A[cur]. Пусть это будет next 2) Если подстрока A[cur] .. A[next] полиндром, то полиндром найден. 3) Находим следующий next 4) Когда все next'ы закончились - увеличиваем cur, и переходим к шагу 1. Мы применяем бинарный поиск N раз что даёт оценку в O(N*log(N)). Худший случай - строка вида AAAA. В лучшем случае (строка ABC) затрачивается Θ(N), этот результат является оптимальным =) Пример. Дана ABABACB 0) A встречается на 1, 3, 5 позиции, B встречается на 2,4,7 позиции C встречается на 6 1) Берём первую A. Следующая A встречается на 3 позиции. Подстрока ABA - полиндром Берём следующую(третью) A. Подстрока ABABA полиндром. Больше A нет 2) Берём B. Следующая B - на 4 позиции BAB полиндром. Следующая B - на 7 позиции, BABACB не полиндром 3) Берём A. Следующая A на 5 позиции. ABA полиндром. Более А нет. 4) Берём B. Следующая B на 7 позиции. BACB не полиндром 5) A на 5 позиции. Далее A нет. 6) С на 6 позиции. Далее C нет 7) B на 7 позиции. Далее B нет. |
| Автор: Akina 17.5.2006, 10:56 |
| Для текста с количеством символов n слов N можно за O(N)+O(n) при условии что весь текст можно загрузить в переменные программы в памяти. 1) Регуляркой или по одному символу заменить все небуквенные символы на пробелы. 2) Регуляркой или мультипроходно заменить группы пробелов на одиночные пробелы. 3) Разбить текст на слова функцией Split в массив. 4) Протестить каждое слово (элемент массива) на str == strreverse(str) . |
| Автор: Psyhonaut 20.5.2006, 13:25 |
Программа написана, всем спасибо за помощь.Тему можно закрывать  |