Найти в данной строке подстроку, которая является палиндромом наибольшей длины - 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
- Выводится сообщение о количестве символов в самом длинном палиндроме
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д