Ошибка сервера в приложении ‘/’.
Описание: На сервере возникла ошибка приложения. Текущая пользовательская настройка ошибок для этого приложения не позволяет удаленно просматривать сведения об ошибке данного приложения (из соображений безопасности). Однако, сведения можно просматривать в браузерах, запущенных на локальном сервере.
Сведения: Для разрешения просмотра сведений данного сообщения об ошибке на локальном сервере создайте тег <customErrors> в файле конфигурации "web.config", который находится в корневом каталоге текущего веб-приложения. В теге <customErrors> следует задать атрибут "mode" со значением "Off".
Примечания: Отображаемую в данный момент страницу ошибок можно заменить на пользовательскую страницу ошибок, изменив атрибут "defaultRedirect" тега конфигурации <customErrors> приложения таким образом, чтобы он содержал URL-адрес пользовательской страницы ошибок.
Решение задачи Палиндромы с Меньшиков
Непустая строка, содержащая некоторое слово, называется палиндромом, если это слово одинаково читается как слева направо, так и справа налево. Пусть дана строка, в которой записано слово S, состоящее из N прописных букв латинского алфавита. Вычёркиванием из этого слова некоторого набора символов можно получить строку, которая будет палиндромом. Требуется найти количество способов вычёркивания из данного слова некоторого (возможно, пустого) набора символов таких, что полученная в результате строка являлась палиндромом. Способы, различающиеся порядком вычёркивания символов, считаются одинаковыми.
Ограничения: 1 Скопировать код
         
Автор: Администратор
Задача о наибольшей подпоследовательности-палиндроме
Например, HELOLEH является подпоследовательностью-палиндромом строки HTEOLFEOLEH.
| Задача: |
| Задача о наибольшей подпоследовательности-палиндроме — это задача о поиске наибольшей подпоследовательности, которую можно получить вычеркиванием некоторых букв из данной последовательности таким образом, что оставшаяся подпоследовательность будет палиндромом. |
Содержание
Решение [ править ]
Обозначим данную последовательность через [math]S[/math] , а ее элементы — через [math]S[i], 0 \leqslant i \leqslant n — 1[/math] , где [math]n[/math] — длина строки [math]S[/math] . Будем рассматривать возможные подпоследовательности данной последовательности с [math]i — [/math] го по [math]j — [/math] ый символ включительно, обозначив её как [math]S(i, j)[/math] . Длины максимальных подпалиндромов для данной последовательности будем записывать в двумерный массив [math]L[/math] : [math]L[i][j][/math] — длина максимальной подпоследовательности-палиндрома, который можно получить из последовательности [math]S(i, j)[/math] .
Начнем решать задачу с простых подпоследовательностей. Для последовательности из одного элемента (то есть подпоследовательности вида [math]S(i, i)[/math] ) ответ очевиден — ничего вычеркивать не надо, такая строка будет искомой подпоследовательностью-палиндромом. Для последовательности из двух элементов [math]S(i, i + 1)[/math] возможны два варианта: если элементы равны, то мы имеем подпоследовательность-палиндром, ничего вычеркивать не надо. Если же элементы не равны, то вычеркиваем любой.
Пусть теперь нам дана подпоследовательность [math]S(i, j)[/math] . Если [math]S[i][/math] и [math]S[j][/math] элементы подпоследовательности не совпадают, то один из них нужно вычеркнуть. Тогда у нас останется подпоследовательность [math]S(i, j — 1)[/math] или [math]S(i + 1, j)[/math] — то есть мы сведем задачу к подзадаче: [math]L[i][j] = \max(L[i][j — 1], L[i + 1][j])[/math] . Если же первый и последний элементы равны, то мы можем оставить оба, но необходимо знать решение задачи [math]S(i + 1, j — 1):L[i][j] = L[i + 1][j — 1] + 2[/math] . Таким образом получаем следующее рекуррентное соотношение:
[math] L[i][j] = \begin
Асимптотика [ править ]
Каждый элемент массива мы вычисляем [math]1[/math] раз за [math]O(1)[/math] обращаясь к уже вычисленным элементам. Так как размер массива [math]n \times n[/math] , то алгоритм работает за [math]O(n^2)[/math]
Пример [ править ]
Рассмотрим решение на примере последовательности ABACCBA. Первым делом заполняем диагональ массива единицами, они будут соответствовать подпоследовательностями [math]S(i, i)[/math] из одного элемента. Затем начинаем рассматривать подпоследовательности длины два. Во всех подпоследовательностях, кроме [math]S(3, 4)[/math] , элементы различны, поэтому в соответствующие ячейки запишем [math]1[/math] , а в [math]L[3][4][/math] — [math]2[/math] .
Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали. Для подпоследовательностей длины [math]3[/math] получаются следующие значения: в подпоследовательности ABA первый и последний элемент равны, поэтому [math]L[0][2] = L[1][1] + 2[/math] . В остальных подпоследовательностях первый и последний элементы различны.
BAC: [math]L[1][3] = \max(L[1][2], L[2][3]) = 1[/math]
ACC: [math]L[2][4] = \max(L[2][3], L[3][4]) = 2[/math]
CCB: [math]L[3][5] = \max(L[3][4], L[4][5]) = 2[/math]
CBA: [math]L[4][6] = \max(L[4][5], L[5][6]) = 1[/math]
Продолжая далее аналогичные рассуждения, заполним все ячейки над диагональю и в ячейке [math]L[0][6][/math] получим ответ — [math]6[/math] .
Если же в задаче необходимо вывести не длину, а саму подпоследовательность-палиндром, то дополнительно к массиву длин мы должны построить массив переходов — для каждой ячейки запомнить, какой из случаев был реализован.
Последовательность заполнения массива и массив переходов см. на изображениях ниже.
Псевдокод [ править ]
Перед вызовом процедуры заполняем [math]L[][][/math] начальными значениями: [math]L[i][j] = 1[/math] если [math]i=j[/math] , [math]L[i][j] = 0[/math] , если [math]i\gt j[/math] , в остальных случаях [math]L[i][j]=-1[/math] . При первом вызове функции в качестве аргументов передаем индексы первого и последнего элементов исходной строки. Например для строки длиной [math] N [/math] вызов функции будет иметь следующий вид: [math] \mathrm