Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
0 / 0 / 0
Регистрация: 07.11.2014
Сообщений: 30
1

Если строка T может быть получена из строки S с помощью циклических сдвигов, выведите искомое число сдвигов

07.11.2014, 15:54. Показов 786. Ответов 4
Метки нет (Все метки)

Вступление
Я хочу рассказать Вам одну историю. Не всю, конечно, а только начало, потому что конец этой истории стал легендой программирования — так же, как и её непосредственные участники.
Когда компьютеры были большими, деревья маленькими, а солнце светило ярче… Короче говоря, жили-были Три Программиста. Вряд ли они участвовали в контестах, поскольку никаких контестов в те далёкие времена ещё не было. Не было ACM ICPC, не было даже Timus Online Judge. А Три Программиста — были.
Задача
Однажды Три Программиста придумали занятную игру для тренировки памяти и умственных способностей. Первый Программист сочинил строку S из N символов и сообщил её Второму и Третьему Программистам. Второй Программист произвёл над этой строкой X (0 ≤ X < N) последовательных циклических сдвигов (под циклическим сдвигом строки понимается перенос её последнего символа в начало). В результате этих манипуляций получилась строка T, которую он сообщил Третьему Программисту. Задачей Третьего Программиста было определить число X, либо сообщить Второму Программисту, что он ошибся, поскольку строка T не могла быть получена из строки S с помощью циклических сдвигов.
Исходные данные
Первая строка содержит целое число N (1 ≤ N ≤ 250000). Вторая строка содержит строку S. Третья строка содержит строку T. Обе строки имеют длину N и могут содержать любые символы таблицы ASCII с кодами от 33 до 255.
Результат
Если строка T может быть получена из строки S с помощью циклических сдвигов, выведите искомое число X, иначе выведите «−1». Если задача имеет несколько решений, можно вывести любое из них.
Подсказка
Рассмотрим строки S = «abracadabra» и T = «racadabraab». Строка T может быть получена из строки S с помощью 9 циклических сдвигов: «abracadabra» > «aabracadabr» > «raabracadab» > «braabracada» > «abraabracad» > «dabraabraca» > «adabraabrac» > «cadabraabra» > «acadabraabr» > «racadabraab».
Может кто-нибудь знает как решить или хотя бы дайте подсказку.Буду благодарен
 Комментарий модератора 
Нарушение правил п5.19 Запрещено создавать темы в виде ссылок на задания или коды программ, расположенные на других сайтах.

 Комментарий модератора 
Еще раз удалите замечание модератора получите красную карту!
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.11.2014, 15:54
Ответы с готовыми решениями:

Создать массив Random. хранить исходный массив в TMemo. Полученное число циклических сдвигов влево
надо создать массив Random . хранить исходный массив в TMemo. полученное число циклических сдвигов...

Осуществить N циклических сдвигов вправо элементов исходного списка
Помогите пожалуйста! Не могу разобраться как сделать задания на lisp 1) Осуществить N...

Какие есть алгоритмы для нахождения циклических сдвигов в строке?
Какие есть алгоритмы для нахождения циклических сдвигов в строке?

Расшифровка сдвигов
Массив a четной длины зашифровали следующим образом: разбили его на 2 части одинаковой длины (левую...

4
2540 / 1199 / 358
Регистрация: 30.11.2013
Сообщений: 3,820
07.11.2014, 16:01 2
А в чём сложность? Почитайте о смещеннии указателя и операторе сравнения
0
0 / 0 / 0
Регистрация: 07.11.2014
Сообщений: 30
07.11.2014, 16:12  [ТС] 3
rikimaru2013, не могу написать в виде программы эти циклические сдвиги

Добавлено через 2 минуты
не хватает еще знания,чтобы написать программу.а задачу надо обязательно решить

Добавлено через 4 минуты
rikimaru2013, спасибо,сейчас почитаю
0
castaway
07.11.2014, 16:20
  #4

Не по теме:

А трёх программистов звали не лебедь, рак и щука?

0
2822 / 1631 / 252
Регистрация: 03.12.2007
Сообщений: 4,222
07.11.2014, 16:45 5
Суть такая:
C++
1
2
3
4
5
6
7
getline(cin, s);
getline(cin, t);
string::size_type pos = (t + t).find(s);
if (pos != string::npos)
    cout << pos;
else
    cout << "-1";
Только поиск, наверное, надо реализовать вручную алгоритмом, который даёт лучшую скорость в худшем случае.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.11.2014, 16:45

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Реализация сдвигов
Пытаюсь выполнить операции сдвига: std::array&lt;byte, 8&gt; Bash::ShHi(std::array&lt;byte, 8&gt; B) {...

Не может быть получена лицензия для запуска программы
Добрый день! Есть сервер W2008R2, на него по usb over ip пробрасывается ключ для по PlanTracer Pro...

Строка: Выведите слово «YES», если ник мог быть использован на эмо-форуме в 2007 году
В 2007 году ник на эмо-форуме должен был обязательно содержать в себе хотя бы одну большую и одну...

Особенности битовых сдвигов
Совершаю два битовых сдвига: а) int x = 5 &gt;&gt; 100; б) int x = 5; printf (&quot;%d&quot;, (unsigned) x &gt;&gt;...

Команды логических операций, сдвигов
Здравствуйте All. Объясните пожалуйста как решить следующую задачу: 1.В исходном байте DataByte...

Команды сравнения и логических сдвигов
Всем привет. Задание: Сравнить содержимое AL с содержимым ячейки памяти 0015Н, если содержимое...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.