#include <stdio.h>
#include <string.h>
int max(int value1, int value2) {
return ( (value1 > value2) ? value1 : value2);
}
int main() {
int k[100][100];
const char *s1 = "ASDDFSA"; // Здесь - твои символы (до 100 штук)
int L = strlen(s1);
char *s2 = strdup(s1);
strrev(s2);
for(int i = 0; i <= L; ++i)
k[0] = k[0] = 0;
for(i = 1; i <= L; ++i)
for(int j = 1; j <= L; ++j)
if(s1[i - 1] == s2[j - 1]) k[j] = k[i - 1][j - 1] + 1;
else k[j] = max(k[i - 1][j], k[j - 1]);
printf("You should delete %i char(s)\n", (L - k[L][L]));
i = L; j = L;
while(k[j]) {
while (k[j - 1] == k[j]) j -= 1;
if(s1[i-1] == s2[j-1]) {
printf("%c", s1[i-1]);
j -= 1;
}
i -= 1;
}
printf("\n");
return 0;
}
[C/C++] строки палиндром
Дана символьная строка, составленная из букв латинского алфавита . Определите наименьшее количество символов , которые необходимо удалить , чтобы из оставшихся получлся палиндром. Укажите удаляемые символы. Текст : "DAKFQNFSK". Рузльтат : нужно выбросить 4 символа , например, N, S, D, A, получится палиндром FKQKF
выкидываем по очереди всевозможные комбинации букв длин 1,2,3...
плюсы - легко реализовать перебором
ну и будет долго работать - если подумать то наверно как то процесс можно оптимизировать
кстати можно и рекурсивно
выкидываем символ смотрим палиндром или нет
если нет то рекурсивный вызов от оставшегося
функция, которая определяет, что строка полинром есть в FAQ'е.
Рекурсивный метод (теория и алгоритм) можно стрельнуть на википедии - Задача "Сделай Палиндром".
Табличный метод, исходник у меня валялся, вроде даже рабочий , правда решал не я ..., но будут вопросы задавай.
Код:
Решение базируется на поиске наибольшей общей подпоследовательности (НОП), алгоритм прямой прогонки. В самом деле, если взять слово в прямом порядке и в обратном порядке, и найти их НОП, то она (подпоследовательность) и будет искомым палиндромом. Массив k - хранит значение максимальных НОП. Очень подробное описание с доказательством можно посмотреть здесь.
По поводу вывода тех букв, которые необходимо удалить тоже невижу особых проблем. Удали из исходной строки те буквы которые есть в палиндроме, оставшиеся выведи.