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