ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1297. Палиндромы

For those who're getting WA19
Послано jagatsastry 18 июн 2008 16:39
You must have found the longest common substring of a and rev(a). That method works. But you should also be taking care of false positives like
rewqSOMETEXTqwer. You get rewq while ETE is the answer. So, once you think it's the end of a possible palindrome, have a checker to make sure that IT IS a palindrome and not a false positive sign.
This is the part of my code which does this(I've used the dp method found in wikipedia)
              if(mxLen<lcs[i][j])
              {

                   if(((i==n || j==n) || a[i]!=b[j]))
                      if(checkIfPali(a, i-1, lcs[i][j]))
                                 {
                                  mxPt=j-1;
                                  mxLen=lcs[i][j];
                                 }
              }

Hope this helps many,
Jagat