Найти в данной строке подстроку, которая является палиндромом наибольшей длины - C (СИ)
Формулировка задачи:
Дается строка. Найти в ней подстроку, которая является палиндромом наибольшей длины. Если их несколько, то можно вывести любую. Посчитать сложность.
Например:
abcbaaaaab -> baaaaab
bdgearlfgs -> NULL
Надеюсь, кто-нибудь может подсказать
Решение задачи: «Найти в данной строке подстроку, которая является палиндромом наибольшей длины»
textual
Листинг программы
#include <stdio.h>
#include <stdlib.h>
#define MIN 3 //минимальная длина палиндрома
void srch(char*);
int main()
{
char str[] = "abcbaaaaabaaaaab";
srch(str);
return 0;
}
void srch(char* ptr)
{
char *first, *last, *N, *head, *tail, *x = NULL, *y = NULL;
unsigned max = 0, flag = 0, count = 0;
puts("The line:");
for(N = ptr; *N; N++)
putchar(*N);
for(first = ptr; first < N - MIN; first++){
for(last = first + MIN; last < N; last++){
if(*last == *first){
for(head = first, tail = last, flag = 0; tail > head; tail--, head++){
if(*head != *tail){
flag = 1;
break;
}
}
if(!flag){
count = last - first + 1;
if(count > max){
max = count;
x = first;
y = last;
}
}
}
}
}
putchar('\n');
if(!x)
puts("Palindrome not found");
else{
puts("The longest palindrome:");
for( ; x <= y; x++)
putchar(*x);
printf("\nhas %u symbols", max);
}
}
Объяснение кода листинга программы
- Подключение необходимых библиотек для работы с файлами и стандартным вводом/выводом
- Объявление минимальной длины палиндрома, которую необходимо найти
- Объявление функции
srch, которая будет осуществлять поиск палиндрома в строке - Объявление основной функции программы
main, в которой происходит вызов функцииsrchи вывод строки на экран - Определение строки, в которой необходимо найти палиндром
- Вывод строки на экран с помощью цикла
forи функцииputchar - В функции
srchинициализация переменных: указателей на начало и конец подстроки, указателей на голову и хвост палиндрома, флага проверки на палиндром, счетчика количества найденных палиндромов и указателей на самый длинный палиндром - Проверка каждого символа строки на равенство следующему за ним символу (проверка на палиндром)
- Если текущий символ равен следующему за ним символу, то начинается проверка на палиндром с помощью указателей на голову и хвост палиндрома
- Если текущий символ не равен следующему за ним символу, то палиндром не найден и счетчик количества найденных палиндромов увеличивается на единицу
- Если текущий палиндром больше предыдущего найденного палиндрома, то обновляются указатели на голову и хвост палиндрома, а также значение счетчика количества найденных палиндромов
- Если в строке не найдено ни одного палиндрома, то выводится сообщение об этом
- Если в строке найден палиндром, то выводится сообщение о нахождении палиндрома с указанием его длины
- Выводится самый длинный палиндром с помощью цикла
forи функцииputchar - Выводится сообщение о количестве символов в самом длинном палиндроме