Найти в данной строке подстроку, которая является палиндромом наибольшей длины - 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);
    }
 
}

Объяснение кода листинга программы

  1. Подключение необходимых библиотек для работы с файлами и стандартным вводом/выводом
  2. Объявление минимальной длины палиндрома, которую необходимо найти
  3. Объявление функции srch, которая будет осуществлять поиск палиндрома в строке
  4. Объявление основной функции программы main, в которой происходит вызов функции srch и вывод строки на экран
  5. Определение строки, в которой необходимо найти палиндром
  6. Вывод строки на экран с помощью цикла for и функции putchar
  7. В функции srch инициализация переменных: указателей на начало и конец подстроки, указателей на голову и хвост палиндрома, флага проверки на палиндром, счетчика количества найденных палиндромов и указателей на самый длинный палиндром
  8. Проверка каждого символа строки на равенство следующему за ним символу (проверка на палиндром)
  9. Если текущий символ равен следующему за ним символу, то начинается проверка на палиндром с помощью указателей на голову и хвост палиндрома
  10. Если текущий символ не равен следующему за ним символу, то палиндром не найден и счетчик количества найденных палиндромов увеличивается на единицу
  11. Если текущий палиндром больше предыдущего найденного палиндрома, то обновляются указатели на голову и хвост палиндрома, а также значение счетчика количества найденных палиндромов
  12. Если в строке не найдено ни одного палиндрома, то выводится сообщение об этом
  13. Если в строке найден палиндром, то выводится сообщение о нахождении палиндрома с указанием его длины
  14. Выводится самый длинный палиндром с помощью цикла for и функции putchar
  15. Выводится сообщение о количестве символов в самом длинном палиндроме

Оцени полезность:

9   голосов , оценка 4 из 5
Похожие ответы