Форум программистов, компьютерный форум CyberForum.ru

Из данной строки удалите наименьшее количество символов, так, чтобы получился палиндром - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Вводится матрица из 0 и 1. Найти в ней прямоугольную подматрицу из одних единиц максимального размера http://www.cyberforum.ru/cpp-beginners/thread847879.html
Срочно до утра нужно построить несколько алгоритмов на С++. Кто может помогите! Вот задания: 5. Вводится матрица a(m,n) (максимум: 5 на 7) из 0 и 1. Найти в ней прямоугольную подматрицу из одних единиц максимального размера (т.е. с максимальным произведением высоты на длину). В качестве результата вывести матрицу, в которой все элементы повторяют элементы исходной матрицы, а элементы...
C++ Связные списки (?) Отсортировать карточки с названиями мест по первой букве Есть студенты, есть большое количество карточек, на каторых написаны названия мест, куда их нужно разослать. Их нужно отсортировать по местам, куда они будут отправлены. Вопрос в том, как большое кол-во карточек отсортировать по местам проживания? Было предложено сначала отсортировать все карточки по первой букве названия места проживания. Затем будет легче отсортировать по самим местам... http://www.cyberforum.ru/cpp-beginners/thread847877.html
C++ Расстолковать задание по ООП С++
Написать саму прогу для меня не проблема,но вот только не совсем пойму задание,непонятна конкретно эта часть :пассажиры перемещаются в самолет, терминал освобождается; в) самолет взлетает, ВПП освобождается. .Тоесть терминал освобождается-это деструктор(удаление объекта),но ведь терминал является полем-и что тут имеется ввиду не понятно,тоесть создать несколько объектов и удалить объект для...
перспективная проекция C++
как перевести 3D координаты в 2D? перспективно не ортогонально. допустим камера всегда находится в координатах 0, 0, 0 и смотрит всегда в направлении z оси камера некогда не изменит своё положение и направление вопрос: как создать перспективную проекцию имея только координаты точки и размер экрана?
C++ В начале строки имеются пробелы и в ней имеются цифры.Найти порядковый номер максимальной цифры,начиная счет с первого символа, не являющегося пробело http://www.cyberforum.ru/cpp-beginners/thread847851.html
Срочно до утра нужно построить несколько алгоритмов на С++. Кто может помогите! Вот задания: 1.Дана строка, вначале которой имеются пробелы и в которой имеются цифры. Найти порядковый номер максимальной цифры, начиная счет с первого символа (считая его первым по номеру), не являющегося пробелом. Если максимальных цифр несколько, то должен быть найден номер первой из них. Пример: Ввод:...
C++ Подскажите пожалуйста как можно упростить! #include <iostream> #include <iomanip> #include <math.h> #include <conio.h> #include <stdio.h> using namespace std; int main() подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
3040 / 1685 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
07.11.2016, 15:44     Из данной строки удалите наименьшее количество символов, так, чтобы получился палиндром
Цитата Сообщение от Babysitter Посмотреть сообщение
что-то такое написал
Вот так несколько побыстрее работает:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
///////////////////////////////////////////////////////////////////////////////
//3.
///////////////////////////////////////////////////////////////////////////////
//Из данной строки удалите наименьшее количество символов
//так, чтобы получился палиндром.
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <map>
#include <string>
#include <utility>
///////////////////////////////////////////////////////////////////////////////
typedef std::string                                 T_str;
typedef T_str::size_type                            T_pos;
typedef T_pos                                       T_len;
typedef std::pair   < T_pos,            T_len   >   T_pos_and_len;
typedef std::map    < T_pos_and_len,    T_str   >   T_palindrom_of_pos_and_len;
///////////////////////////////////////////////////////////////////////////////
bool    ends_equal
    (
        T_str           const   &   s,
        T_pos_and_len   const   &   pos_and_len
    )
{
    auto    pos     =   pos_and_len.first;
    auto    len     =   pos_and_len.second;
 
    return      s[ pos              ]
            ==  s[ pos + len - 1    ];
}
///////////////////////////////////////////////////////////////////////////////
T_str   get_palindrom_of_pos_and_len
    (
        T_str                       const   &   s,
        T_palindrom_of_pos_and_len          &   palindrom_of_pos_and_len,
        T_pos_and_len               const   &   pos_and_len
    )
{
    auto    it  =   palindrom_of_pos_and_len.find( pos_and_len );
 
    if  (
            it  !=  palindrom_of_pos_and_len.end()
        )
    {
        return  it->second;
    }
 
    T_str   res;
    auto    pos     =   pos_and_len.first;
    auto    len     =   pos_and_len.second;
 
    if  (
                len
            <=  1
        )
    {
        res     =   s.substr( pos, len );
    }
    else if (
                ends_equal( s, pos_and_len )
            )
    {
        res     =       s[ pos ]
 
                    +   get_palindrom_of_pos_and_len
                            (
                                s,
                                palindrom_of_pos_and_len,
 
                                {
                                    pos     +   1,
                                    len     -   2
                                }
                            )
 
                    +   s[ pos ];
    }
    else
    {
        auto    L   =   get_palindrom_of_pos_and_len
                            (
                                s,
                                palindrom_of_pos_and_len,
 
                                {
                                    pos,
                                    len     -   1
                                }
                            );
 
        auto    R   =   get_palindrom_of_pos_and_len
                            (
                                s,
                                palindrom_of_pos_and_len,
 
                                {
                                    pos     +   1,
                                    len     -   1
                                }
                            );
 
        res     =       L.size()
                    >   R.size()
                        ?   L
                        :   R;
    }//else
 
    palindrom_of_pos_and_len[ pos_and_len ]   =   res;
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
T_str   max_palindrom( T_str    const   &   s )
{
    T_palindrom_of_pos_and_len  palindrom_of_pos_and_len;
 
    return  get_palindrom_of_pos_and_len
                (
                    s,
                    palindrom_of_pos_and_len,
 
                    {
                        0,
                        s.size()
                    }
                );
}
///////////////////////////////////////////////////////////////////////////////
T_str   rand_str_with_size( int  size )
{
    const   T_str   LETTERS     =   "abcdefghijklmnopqrstuvwxyz";
    T_str           res;
 
    for( int  i{}; i < size; ++i )
    {
        res     +=  LETTERS[ rand() % LETTERS.size() ];
    }
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    srand(unsigned(time(0)));
 
    for(;;)
    {
        T_str   s   =   rand_str_with_size(2000);
 
        std::cout   <<  std::endl
                    <<  std::endl
                    <<  s
                    <<  std::endl
                    <<  std::endl
                    <<  "-> ";
 
        T_str   res     =   max_palindrom(s);
 
        std::cout   <<  res
                    <<  std::endl;
 
        system("pause");
    }//for
}
 
Текущее время: 23:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru