Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.69/13: Рейтинг темы: голосов - 13, средняя оценка - 4.69
Игогошка!
 Аватар для ct0r
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367

Задачка для новичков #3: определить, является ли строка палиндромом

21.08.2016, 15:02. Показов 3346. Ответов 37
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Простенькая задачка, нужно запилить нормальный плюсовый код.

Юзер посимвольно вводит строку, прога должна определять, является ли введенное палиндромом:

a - yes (юзер ввел a)
ab - no (потом юзер ввел b)
abb - no (снова ввел b и так далее)
abbc - no
abbcb - no
abbcbb - no
abbcbba - yes
...

Юзер (а может и бот) может быть очень настойчивым и вводить строку годами (или копипастить большой текст откуда-то), поэтому прога должна быстро отвечать
 Комментарий модератора 
В названии темы должно быть указано что в ней, а не для кого она.
3
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
21.08.2016, 15:02
Ответы с готовыми решениями:

Для каждой строки заданного текста определить, является ли строка палиндромом.
Дан текст (массив строк) в котором каждая строка содержит до 255 цифр. Составить программу, которая для каждой строки определяет, является...

Пользователем вводится строка. Программа должна определить, является ли эта строка палиндромом
Пользователем вводится строка.программа должна определить , является ли эта строка полиндромом ?

Определить является ли строка палиндромом
нужно определить для даного рядка есть ли этот рядок симметричным. также вторым ответом для этого же рядка нужно вывести есть ли этот рядок...

37
Игогошка!
 Аватар для ct0r
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
21.08.2016, 17:08  [ТС]
Студворк — интернет-сервис помощи студентам
rikimaru2013, "abcabc"?
0
:)
Эксперт С++
4773 / 3267 / 497
Регистрация: 19.02.2013
Сообщений: 9,046
21.08.2016, 21:16
Новичок, что насчет коллизий?
Кстати, код сбоит на "aaaaaaaaaaaaa":
1
183 / 181 / 66
Регистрация: 15.02.2015
Сообщений: 515
21.08.2016, 21:44
Цитата Сообщение от ct0r Посмотреть сообщение
вводить строку годами (или копипастить большой текст откуда-то)
Текст весь хранить в памяти можно? ))
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <string>
 
using namespace std;
 
class IsPolindrom
{
public:
    IsPolindrom();
    bool push(const char ch);
    bool push(const char* ch);
    const char* get() const;
 
private:
    string buf;
    bool is_polindrom() const;
};
 
IsPolindrom::IsPolindrom()
{
    buf.reserve(1024);
}
 
const char* IsPolindrom::get() const
{
    return buf.c_str();
}
 
bool IsPolindrom::push(const char ch)
{
    
    buf.push_back(ch);
    return is_polindrom();
}
bool IsPolindrom::push(const char* str)
{
    buf += str;
    return is_polindrom();
}
bool IsPolindrom::is_polindrom() const
{
    auto head = buf.begin();
    auto tail = buf.rbegin();
    for (size_t i = 0, l = (buf.length() + 1) / 2; i < l; ++i) {
        if (*head++ != *tail++)
            return false;
    }
    return true;
}
 
int main()
{
    IsPolindrom is_p;
    while (true) {
        string str;
        cin >> str;
        bool ret = is_p.push(str.c_str());
        cout << is_p.get() << (ret ? " - yes!" : " - no") << endl;
    }
    return 0;
}
0
Игогошка!
 Аватар для ct0r
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
21.08.2016, 21:53  [ТС]
Tulosba, там переполняется просто, лучше так чуть-чуть изменить
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
int main() {
    string s;
    cin >> s;
    const uint64_t MOD = 2e10, p = 31;
    uint64_t p_pow = 1,
              hash = 0, reverse_hash = 0;
    for (size_t i = 0; i < s.size(); i++) {
        hash = (hash + s[i] * (p_pow % MOD)) % MOD;
        reverse_hash = (reverse_hash * p + s[i]) % MOD;
        cout << (hash == reverse_hash ? "Yes\n" : "No\n");
        p_pow *= p;
    }
}
Про коллизии я уже писал - если нужен всегда 100% верный ответ, то после совпадения хэшей нужно проверить строку как обычно.
0
2549 / 1208 / 358
Регистрация: 30.11.2013
Сообщений: 3,826
21.08.2016, 21:56
ct0r,
Кликните здесь для просмотра всего текста
так вы правильный/свой ответ покажите ? Я как понимаю ответ Rolling hash ?
0
Игогошка!
 Аватар для ct0r
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
21.08.2016, 22:41  [ТС]
Operok, это медленное решение, которое уже предлагали, - для каждого нового символа приходится смотреть всю строку.

Цитата Сообщение от rikimaru2013 Посмотреть сообщение
так вы правильный/свой ответ покажите ?
Показать прям, как правильно уже известный алгоритм закодировать?

Добавлено через 40 минут
Решение:
Кликните здесь для просмотра всего текста
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
#include <cassert>
#include <cstdint>
#include <iostream>
#include <string>
 
void OGOGO(const std::string& s) {
  assert(!s.empty());
    
  std::cout << "yes " << s[0] << '\n';
 
  if (s.length() == 1)
    return;
    
  constexpr std::uint32_t Q {129};
  constexpr std::uint32_t D {256};
 
  std::int64_t fstr {s[0] % Q};
  std::int64_t snd {s[1] % Q};
  std::int64_t h {1};
 
  for (std::size_t i {1}; i < s.length(); ++i) {
    if (fstr == snd) {
      std::size_t j {0};
      while (j < i/2) {
        if (s[j] != s[i-j])
          break;
        ++j;
      }
      std::cout << (j == i/2 ? "yes " : "no ");
    } else {
      std::cout << "no ";
    }
    std::cout << s[i] << '\n';
 
    if (i != s.length() - 1) {
      if (i % 2 == 0) {
        h = (h * D) % Q;
        fstr  = (fstr + h * s[i / 2]) % Q;
        snd = (snd * D + s[i + 1]) % Q;
      } else {
        snd = (D * (snd + Q - s[(i + 1) / 2] * h) % Q + s[i + 1]) % Q;
      }
    }
  }
}
 
int main() {
  OGOGO("abbcbba");
}
3
:)
Эксперт С++
4773 / 3267 / 497
Регистрация: 19.02.2013
Сообщений: 9,046
21.08.2016, 22:41
Цитата Сообщение от ct0r Посмотреть сообщение
там переполняется просто
Так "чуть-чуть" измененный тоже "переполняется".
И "решение" сбоит.
1
2549 / 1208 / 358
Регистрация: 30.11.2013
Сообщений: 3,826
21.08.2016, 22:50
Tulosba, так ему так!!!!! Задал задачку, а ответа не знает!!!!!
0
 Аватар для Новичок
1682 / 1098 / 489
Регистрация: 17.07.2012
Сообщений: 5,361
21.08.2016, 22:59
Лучший ответ Сообщение было отмечено ct0r как решение

Решение

Так вроде нормально работает
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
int main() {
    string s;
    //cin >> s;
    s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
    const uint64_t MOD = 1e17, p = 31;
    uint64_t p_pow = 1,
              hash = 0, reverse_hash = 0;
    for (size_t i = 0; i < s.size(); i++) {
        hash = (hash + s[i] * (p_pow % MOD)) % MOD;
        reverse_hash = (reverse_hash * p + s[i]) % MOD;
        cout << (hash == reverse_hash ? "Yes\n" : "No\n");
        p_pow = p_pow * p % MOD;
    }
}
0
2549 / 1208 / 358
Регистрация: 30.11.2013
Сообщений: 3,826
21.08.2016, 23:03
Новичок,
Кликните здесь для просмотра всего текста
0
 Аватар для Новичок
1682 / 1098 / 489
Регистрация: 17.07.2012
Сообщений: 5,361
21.08.2016, 23:10
rikimaru2013, странно, у меня в CodeBlocks все пашет, да и в ideone нормально работает.
http://ideone.com/gd2tJi
0
2549 / 1208 / 358
Регистрация: 30.11.2013
Сообщений: 3,826
21.08.2016, 23:13
Новичок,
http://rextester.com/TWM75868 gcc
http://rextester.com/HGR31511 clang
http://rextester.com/PGR90994 vc++

Все говорят, что вам код не очень - кому верить?(
0
 Аватар для Новичок
1682 / 1098 / 489
Регистрация: 17.07.2012
Сообщений: 5,361
21.08.2016, 23:21
rikimaru2013, чет мне кажется вы там ввели одну русскую букву "р", а все остальные английские.
1
2549 / 1208 / 358
Регистрация: 30.11.2013
Сообщений: 3,826
21.08.2016, 23:29
Новичок,
Кликните здесь для просмотра всего текста

А я такой, что мог!!!

0
Игогошка!
 Аватар для ct0r
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
21.08.2016, 23:43  [ТС]
Цитата Сообщение от rikimaru2013 Посмотреть сообщение
Задал задачку, а ответа не знает!!!!!
Ну давай-давай, шломай!
Кликните здесь для просмотра всего текста
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
#include <cassert>
#include <cstdint>
#include <iostream>
#include <string>
 
void checkPalindromes(const std::string& s) {
  constexpr std::int64_t Q {1103515245};
  constexpr std::int64_t D {256};
    
  assert(!s.empty());
    
  std::cout << "yes " << s[0] << '\n';
 
  if (s.length() == 1)
    return;
 
  std::int64_t fstr {s[0] % Q};
  std::int64_t snd {s[1] % Q};
  std::int64_t h {1};
 
  for (std::size_t i {1}; i < s.length(); ++i) {
    if (fstr == snd) {
      std::size_t j {0};
      while (j < i/2) {
        if (s[j] != s[i-j])
          break;
        ++j;
      }
      std::cout << (j == i/2 ? "yes " : "no ");
    } else {
      std::cout << "no ";
    }
    std::cout << s[i] << '\n';
 
    if (i != s.length() - 1) {
      if (i % 2 == 0) {
        h = (h * D) % Q;
        fstr = (fstr + h * s[i / 2] % Q) % Q;
        snd = (snd * D % Q + s[i + 1]) % Q;   
      } else {
        snd = (D * (snd + Q - s[(i + 1) / 2] * h % Q) % Q + s[i + 1]) % Q;
      }
    }
  }
}
 
int main() {
  checkPalindromes("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
}
1
2549 / 1208 / 358
Регистрация: 30.11.2013
Сообщений: 3,826
22.08.2016, 00:06
ct0r,
Кликните здесь для просмотра всего текста
Сдаюсь - пробовал сломать - но даже : djdjdjjfjfdijosmcgdfhmsuighcuisdhcdfsdcfsdfsdxfzsdfgcsdhtyjvuyrkuyjuyjuyjuyjyubuybjuyguisdmfucgducgmsdfucgmsdfuhmsdcgusdmfucghsudfcgsdfhmcgffgcmhfdsgcfdushgcufmdsugcdsmhufdsmgcufdsmgcudgcufmdsiugyujbyubuyjyujyujyujyukryuvjythdscgfdszfxdsfdsfcdsfdchdsiuchgiusmhfdgcmsojidfjfjjdjdjd и тот осилил. Сильно)
0
 Аватар для Kastaneda
5232 / 3206 / 362
Регистрация: 12.12.2009
Сообщений: 8,143
Записей в блоге: 2
22.08.2016, 09:09
ct0r, так все же как алгоритм называется? Чтоб знать на будущее.

Добавлено через 25 секунд

Не по теме:

rikimaru2013, ты разметку форума сломал :D

0
Игогошка!
 Аватар для ct0r
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
22.08.2016, 10:03  [ТС]
Kastaneda, это просто модификация алгоритма Рабина-Карпа.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
22.08.2016, 10:03

Определить является ли строка палиндромом
Дана строка, возможно, содержащая пробелы. Определите, является ли эта строка палиндромом, при условии, что заглавные и строчные буквы не...

Определить, является ли строка палиндромом
По данной строке определите, является ли она палиндромом (то есть, можно ли прочесть ее наоборот, как, например, слово &quot;топот&quot;). ...

Определить, является ли строка палиндромом
У вас есть строка. Определить, погоду это palindrom или нет. Palindrom это слова, которые можно читать слева направо же, как и справа...

Определить, является ли строка палиндромом
#include &lt;stdio.h&gt; #include &lt;string&gt; //Позволяет испльзовать ф-ю strlen() - получить длину #include...

Определить, является ли строка палиндромом
Определить, является ли строка палиндромом (без учета пробелов, знаков препинания и регистра).


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
38
Ответ Создать тему
Новые блоги и статьи
Как установить и настроить Windows 11 без подключения к Интернету и без аккаунта Microsoft
Maks 22.11.2026
Положу сюда, чтобы не искать постоянно. • На экране «Давайте подключим вас к сети» во время установки Windows 11 нажмите комбинацию клавиш Shift+F10, чтобы открыть командную строку. Введите. . .
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru