Технический форум
Вернуться   Технический форум > Программирование > Форум программистов > Помощь студентам


Ответ
 
Опции темы Опции просмотра
Старый 12.06.2016, 16:01   #1 (permalink)
Asya_inter
Member
 
Аватар для Asya_inter
 
Регистрация: 12.01.2015
Сообщений: 71
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
По умолчанию Ускорение программы работающей со строками

Подскажите, как быстрее сделать? Какие вообще есть быстрые способы решения? Моё решение выходить за границу времени.
Слова
(Время: 1 сек. Память: 16 Мб Сложность: 48%)
Для шифрования слов с ними можно производить множество различных операций. Например, интересна такая операция: первые несколько букв заданного слова приписываются к его концу в обратном порядке, после чего удаляются из начала слова. При этом слово a1a2 … akak+1 … an переходит в слово ak+1 … anakak-1 … a1 (число k выбирается в диапазоне от 0 до n).

Для двух заданных слов требуется определить, можно ли применением описанной операции преобразовать первое слово во второе.

Входные данные


Входной файл INPUT.TXT состоит из двух строк - на первой из них записано исходное слово, а во второй - предполагаемый результат. Длины строк не превышают 50000 символов.

Выходные данные


В первой строке выходного файла OUTPUT.TXT выведите "Yes", если преобразование возможно, и "No", если нет. В случае положительного ответа во второй строке выведите k - длину перемещаемой части исходного слова k (из всех таких k выберите минимальный).

Моё решение:
Код:
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int main(){
    string Str2 = "";
    int i = 0, p=0;
    string Strok1 , Strok2; // <50000
    cin >> Strok1 >> Strok2;
    if (Strok1 == Strok2)
    {
        cout << "Yes" << endl << 0;
        return 0;
    }
        int rs = Strok1.size();
    for (i = 1; i <= rs/2; i++)
    {       
        Str2 = Strok1[i - 1] + Str2;
        if (Strok1[i - 1] != Strok2[rs - i])
        {
            cout << "No";
            return 0;
        }
            if (Strok1.substr(i, rs - i)+Str2 == Strok2)
            {
                cout << "Yes" << endl << i;
                return 0;
            }
    }
        cout << "No";
    return 0;
}
Asya_inter вне форума   Ответить с цитированием

Старый 12.06.2016, 16:01
Helpmaster
Member
 
Аватар для Helpmaster
 
Регистрация: 08.03.2016
Сообщений: 0

Я уверен, что проблему можно решить гораздо быстрее если ознакомиться с ней получше

Перенос работающей опер. системы на другой комп.
Ускорение directdraw и ускорение текстур agp недоступно.
Проблемы с 3D графикой работающей с DirectX 9
Как правильно отключать монитор при работающей видюхе?

Ads

Яндекс

Member
 
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
Ответ

Метки
задача, помощь, строки

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Выкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.




Часовой пояс GMT +4, время: 20:23.

Powered by vBulletin® Version 6.2.5.
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.