Найдите самую длинную непалиндромную подстроку в строке

Мне нужно найти самую длинную непалиндромную подстроку (строку, которая сама по себе не является палиндромом, независимо от того, является ли она какой-либо подстрокой) в строке за O (n ** 2) или меньше времени.

Я могу придумать простой алгоритм грубой силы, находя все возможные подстроки (O (n ** 2)), а затем для каждой такой подстроки проверяя, является ли это палиндромом (O (n)), принимая общую сложность до O ( n ** 3).

Существует O (n ** 2) вариантов определения самой длинной палиндромной подстроки и последовательности, но я не могу повторно использовать их, чтобы найти решение здесь.

Как мне сделать это за O (n ** 2) время?


string algorithm palindrome
person SexyBeast    schedule 11.04.2016    source источник
comment
Подсказка: если вы удалите первый символ из палиндрома, вы получите что-то, что не является палиндромом, за исключением одного очень специфического семейства случаев, которое легко обнаружить.   -  person John Dvorak    schedule 11.04.2016
comment
Что такое непалиндромная подстрока? Подстрока, которая сама по себе не является полным палиндромом? Потому что в этом случае проблема кажется довольно простой. Попробуйте проработать это на бумаге с помощью нескольких примеров.   -  person biziclop    schedule 11.04.2016
comment
Отредактированный вопрос. Да, Ян, я знаю. Конкретный набор - вот что меня беспокоит.   -  person SexyBeast    schedule 11.04.2016
comment
Почему именно этот набор вас беспокоит? Подскажите, как вы думаете, что это за набор?   -  person John Dvorak    schedule 11.04.2016
comment
Насколько я понимаю, существует множество способов получить непалиндромную подстроку из самой длинной палиндромной подстроки - добавление символов в начале или в конце, удаление символов с начала внутри или с конца, или выполнение оба. Не могу понять.   -  person SexyBeast    schedule 11.04.2016
comment
Не начинайте с самой длинной палиндромной подстроки, это только усложняет ситуацию. Ян Дворжак намекает на простой способ решить эту проблему за O (n).   -  person interjay    schedule 11.04.2016
comment
В частности, в среднем это O (1).   -  person John Dvorak    schedule 11.04.2016
comment
@JanDvorak Сначала вам нужно проверить, является ли исходная строка палиндромом, это O(n)   -  person biziclop    schedule 11.04.2016
comment
Исходная строка не является палиндромом, мы не можем полагаться на то, что она является палиндромом.   -  person SexyBeast    schedule 11.04.2016
comment
@AttitudeMonger Если ваша исходная строка не является палиндромом, решение тривиально: ваш ответ - сама строка. Итак, предположим, что это палиндром. Какие свойства должен иметь этот палиндром, чтобы оставаться палиндромом после того, как вы удалили первую букву?   -  person biziclop    schedule 11.04.2016

Ответы (2)


arrow_upward
6
arrow_downward

Поскольку ответ уже опубликован, позвольте мне превратить мои подсказки в настоящий ответ:

Сначала проверьте, является ли полная строка:

  • палиндром (O (n), со средним случаем O (1))
  • повторение одного и того же символа, например «аааааааааааа» (выполняется в том же цикле).

Потом:

  • если строка не является палиндромом, самая длинная подстрока, не являющаяся палиндромом, - это сама строка
  • если строка является палиндромом, но не повторением одного и того же символа, то удаление любого конца сделает ее непалиндромом, и самая длинная такая подстрока
  • если строка является повторением одного и того же символа, то в ней нет подстроки, не являющейся палиндромом. В качестве альтернативы, в зависимости от вашего определения палиндрома, единственная подстрока, не являющаяся палиндромом, - это пустая подстрока.
person Community    schedule 11.04.2016
comment
Хм, верно. Это выглядит довольно законченным. Дайте мне посмотреть, не пропало ли что-нибудь. - person SexyBeast; 11.04.2016

arrow_upward
-2
arrow_downward

Пусть s, e - позиции в строках.

Вы можете определить, является ли подстрока s, e палиндромом, по проверкам string[s] == string[e], а подстрока s + 1, e-1 также является палиндромом (в особом случае одиночные символы s==e и пустые строкиs>e имеют значение true).

Итак, самая простая реализация - создать рекурсивную функцию, как описано выше, и запомнить результаты (сохранить их во внешней матрице).

Вы также можете сделать это итеративно, если будете осторожны с вашей итерацией (так что вам нужны только результаты, предварительно вычисленные).

Оба будут заполнять O (N ^ 2), и отдельные вычисления тривиальны.

person Sorin    schedule 11.04.2016