VPF::Доделать поиск наибольшего палиндрома

nikitosoleil

Дата 3.11.2015, 19:10 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 3.11.2015

Репутация: нет
Всего: нет

Сделал работающую в половине случаев программу на поиск наибольшего палиндрома. Несколько часов не могу найти ошибку, вызывающую сбой во второй половине случаев.

Код


#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
#include <iomanip>
 
using namespace std;
 
const int MAX=1001;
 
int arr[MAX][MAX];
string s1, s2, temps;
char temp;
 
int maximum(int, int);
 
int main()
{
    cin >> s2;
    temp=s2[0];
    temp=tolower(temp);
    s2[0]=temp;
    s1=s2;
    reverse(s2.begin(), s2.end());
    arr[1][1]=0; arr[0][0]=0;
    for (int i=1; i<=s2.length(); i++)
    {
        arr[0][i]=0;
        for (int j=1; j<=s1.length(); j++)
        {
            arr[j][0]=0;
            if (s1[j-1]!=s2[i-1]) arr[j][i]=maximum(arr[j-1][i], arr[j][i-1]);
            else arr[j][i]=arr[j-1][i-1]+1;
        }
    } ///Результат действия сего кода - таблица, которая будет на экране
    int x=s2.length(), y=s1.length();
    while(x!=0&&y!=0) ///Вот тут начинаются попытки восстановить слово
    {
        if (arr[x][y-1]!=arr[x][y] && arr[x-1][y]!=arr[x][y] && arr[x-1][y-1]!=arr[x][y] )
        {
            temps+=s1[x-1];
            x--; y--;
        }
        else if(arr[x-1][y]>arr[x][y-1]) x--;
        else y--;
    }
 
    { ///Вывод таблицы на экран
        cout << "   ";
        for (int j=1; j<=s1.length(); j++) cout << setw(2) << s1[j-1] << " ";
        cout << endl << endl;
        for (int i=1; i<=s2.length(); i++)
        {
            cout << s2[i-1] << "  ";
            for (int j=1; j<=s1.length(); j++)
                cout << setw(2) << arr[j][i] << " ";
            cout << endl;
        }
    }
 
    temp=temps[0];
    temp=toupper(temp);
    temps[0]=temp;
    cout << arr[s1.length()][s1.length()] << endl;
    cout << temps << endl;
 
    { ///Для удобства проверки на правильность
        string ts1, ts2;
        for (int i=0; i<temps.length()/2; i++)
            cout << temps[i];
        cout << endl;
        for (int i=temps.length()-1; i>=temps.length()/2; i--)
            cout << temps[i];
        //cout << endl << ts1 << endl << ts2 << endl;
        //if (ts1==ts2) cout << "True"; else cout << endl << "False" << endl;
    }
 
    return 0;
}
 
int maximum (int a, int b)
{
    if (a>b) return a;
    return b;
}

Если вкратце - реализация задачи на наибольшую общую подпоследовательность, но вторая строка - перевернутая первая. Буду сказочно благодарен.

volatile

Дата 4.11.2015, 12:12 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 16
Всего: 85

Цитата(nikitosoleil @ 3.11.2015, 19:10

)

const int MAX=1001;

int arr[MAX][MAX];

здесь мы съели 4 метра памяти.
Не слишком ли дофига для такой простой задачи?

Это все можно сделать гораздо проще.
Я бы сделал функцию определяющую полиндром это или нет

Код


bool is_polindrom (const std::string & s);

А в основной программе подавать туда строку, постепенно сокращая ее справа

Это сообщение отредактировал(а) volatile - 4.11.2015, 12:14

feodorv

Дата 4.11.2015, 14:00 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(volatile @ 4.11.2015, 12:12

)

Не слишком ли дофига для такой простой задачи?

Наверное, это реализация подобного алгоритма, работающего за O(n^2), где n - длина строки. Я, честно говоря, даже понять не могу, что там в коде происходит...

Это сообщение отредактировал(а) feodorv - 4.11.2015, 14:08

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

feodorv

Дата 4.11.2015, 14:22 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Можно подсмотреть идеи по тривиальному алгоритму или даже по линейному алгоритму здесь. Дополнительной памяти не потребуется вообще.

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

volatile

Дата 4.11.2015, 14:27 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 16
Всего: 85

Цитата(feodorv @ 4.11.2015, 14:00

)

Наверное, это реализация подобного алгоритма

а, тогда сорри. (я не правильно понял задание).

volatile

Дата 4.11.2015, 14:46 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 16
Всего: 85

feodorv, по второй ссылке другая задача, насколько я понял .
В первой они могут выкидывать символы из середины, во второй нет.

Это сообщение отредактировал(а) volatile - 4.11.2015, 14:47

feodorv

Дата 4.11.2015, 15:19 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(volatile @ 4.11.2015, 14:46

)

по второй ссылке другая задача

Да, прошу прощения smile

Вот и вопрос: нужна подпоследовательность непрерывная, или выдернутая из последовательности?

Это сообщение отредактировал(а) feodorv - 4.11.2015, 15:22

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »