Поиск самого длинного палиндрома-подстроки через перебор всех подстрок

Question

Поиск самого длинного палиндрома-подстроки через перебор всех подстрок

Рейтинг: 0Ответов: 1Опубликовано: 01.02.2023

Некоторые подстроки выводятся правильно, а вот в некоторых в конце происходит что-то непонятное. Ну и палиндромы в подстроках ищутся как-то не так, хотя алгоритм проверки работает нормально, если просто вводить её

void longest_palindrome(char *str, char *result)
{
    printf("result = %s\n", result);
    memset(result, 0, strlen(result) - 1);
    printf("result = %s\n", result);    
    char ls[STR_BUFFER + 1];
    _cpystr(ls, str, 1);
    char sub[STR_BUFFER + 1];
    if (isPalindrome(str))
    {
        _cpystr(result, str, strlen(str));
        return;
    }   
    for (int i = 0; i < strlen(str) - 1; i++)
    {   
        for (int j = 1; j < strlen(str); j++)
        {
            if (i + j <= strlen(str))
            {
                printf("i = %d, j = %d ", i, j);
                substr(str, i, j, sub);
                printf("%s\n", sub);
                if ((isPalindrome(sub)) && (strlen(sub) > strlen(ls)))
                {
                    memset(ls, 0, strlen(ls) - 1);
                    _cpystr(ls, sub, strlen(sub) - 1);
                }
                memset(sub, 0, strlen(sub));    
            }
            else
            {
                continue;
            }
        }
    }
    if (strlen(result) == 1)
    {
        strncpy(result, ls, strlen(ls) - 1);
    }
}

int isPalindrome(char *str)
{
    if (strlen(str) < STR_BUFFER)
    {
        char dst[STR_BUFFER];
        int j = 0;
        for (int i = strlen(str) - 2; i >= 0; i--, j++)
        {
            dst[i] = str[j];
        }   
        return (strncmp(str, dst, strlen(str) - 1) == 0);
    }
    else
    {
        exit(BUFFER_OVERFLOW);
    }
}

void _cpystr(char *dst, char *src, size_t cnt)
{
    for (int i = 0; i < cnt; i++)
    {
        dst[i] = src[i];
    }   
}

void substr(char *s, int a, int b, char *t) 
{
    strncpy(t, s + a, b);
}

c# gcc

Источник: Stack Overflow на русском

Answer 1

▲ 2

Код приведен не весь. Но и тут возникает много вопросов.
Зачем вы на каждом шаге делаете копирование строки? Вам вообще не нужно копирование, т.к. вы не изменяете строку. Ну и функции void _cpystr() и void substr() тоже не нужны.
Любую подстроку вы можете выразить как 2 указателя (или 2 индекса) на начало и конец подстроки. А проверка на палиндром - в цикле проверяете равны ли символы, на которые указывают указатели/индексы

// вариант с индексами
bool isPalindrome(const char *str, int begin, int end)
{
    while( begin < end )
        if( str[begin] == str[end] )
        {
            begin++;
            end--;
        }
        else
            return false;
    return true;
}

При поиске наибольшего палиндрома вложенный цикл должен начинаться не с 1, а со значения внешнего цикла +1. Иначе у вас получатся неверные сравнения и неправильное копирование.

for (int i = 0; i < strlen(str) - 1; i++)
//    for (int j = 1; j < strlen(str); j++) // неправильно
    for (int j = i+1; j < strlen(str); j++) // правильно

Логику if( i+j <= strlen(str) ) лучше вынести в условие вложенного цикла - будет меньше сравнений, просто цикл закончится. А в вашем случае он продолжается до конца, но действий не выполняется.

for (int i = 0; i < strlen(str) - 1; i++)
    for (int j = i+1; i+j <= strlen(str); j++) //

Ну и поиск наибольшего палиндрома сводится к перебору всех подстрок и проверке на палиндром, без копирований строк.

    int begin, end; // начало и конец максимального палиндрома в исходной строке
    int max = -1; // длина максимального палиндрома
    int len = strlen(str);
    for(int i=0; i<len-1; i++)
        for( int j=len-1; j>i; j--)
            if( isPalindrome(str, i, j) and max < j-i)
            { 
                max = j-i;
                begin = i;
                end = j;
            }

Можно добавить небольшую оптимизацию. Во внутреннем цикле сначала находить в строке символ, равный символу str[i] и только потом проверять на палиндром. Ну и размер проверять до проверки на палиндром.

if(str[i]==str[j] and max < j-i and isPalindrome(str, i, j) )
{ }

По поводу лишних символов в выводе. Вы создаете буфер для строки char sub[STR_BUFFER + 1];. После создания он заполнен всякими неизвестными символами. А потом при копировании строк в void substr() вы копируете определенное количество символов и не копируете завершающий \0. А на следующей итерации буфер обнуляется, но не весь, а по размеру строки и такая ситуация может повториться. Т.е. нужно добавить обнуление буфера после его создания. Либо изменить функцию копирования строк и дописывать завершающий строку 0 в void substr(), т.к. функция strncpy() если копируется символов меньше, чем в источнике, сама 0 не дописывает. Эта же проблема у вас в функции void _cpystr().

void substr(char *s, int a, int b, char *t) 
{
    strncpy(t, s + a, b);
    t[b] = 0;  // дописывать завершающий строку 0
}

void longest_palindrome(char *str, char *result)
{
    char sub[STR_BUFFER + 1];
    memset(sub, 0, sizeof(sub)); // нужно добавить
    ....
         {
                printf("i = %d, j = %d ", i, j);
                substr(str, i, j, sub);
                printf("%s\n", sub);
                ....
                memset(sub, 0, strlen(sub));
         }    
}

И когда вы обнуляете буфер, лучше обнулять его весь. Иначе у вас опять могут всплыть артефакты.

memset(sub, 0, strlen(sub));  // не так
memset(sub, 0, sizeof(sub));  // а вот так

[n;092$35m/]  // был буфер
[123\02$35m/]  // записали в него строку 123 с завершающим 0
[\0\0\0\02$35m/]  // обнулили до конца строки memset(sub, 0, strlen(sub)), длина строки была 3 
[12345$35m/]  // записали в него 12345 без завершающего 0 - получилось не то, что вы хотели

То решение, которое я написал, вообще не делает ни одного копирования. Поэтому этих ошибок не будет.

Поиск самого длинного палиндрома-подстроки через перебор всех подстрок

Ответы