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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
XXXaker
3 / 3 / 1
Регистрация: 30.06.2010
Сообщений: 43
#1

Оптимизация алгоритма - C++

05.12.2010, 17:38. Просмотров 355. Ответов 0
Метки нет (Все метки)

Вот задачка:
Дана куча строк. Далее заданы запросы, представляющие собой некоторые строки. Для каждого префикса каждого запроса необходимо вывести количество строк в куче, которые имеют такое же начало, как и префикс запроса.

Входные данные: В первой строке содержится два целых числа N и М – количество строк в куче и количество запросов. (1 <= N, M <= 10^5). Далее записаны N строк кучи. Далее содержится строк M запросов. Все строки состоят из маленьких латинских букв. Длина любой строки ввода не превышает 21 символ.

Выходные данные: Для каждого запроса выведите в отдельной строке L чисел через пробел, где L – длина строки запроса. Каждое i-ое число должно содержать ответ задачи для префикса длины i строки запроса.

Пример входных данных
3 4
abacaba
dabaduba
abad
abac
aba
dab
adcb

Пример выходных данных
2 2 2 1
2 2 2
1 1 1
2 0 0 0
вот мой код:
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
#include <iostream>
#include <string>
#include <vector>
#include <ctime>
using namespace std;
 
vector <string> str_masN, str_masM;
 
int main()
{
    int n, m;
    cin >> n >> m;
    str_masN.resize(n);
    str_masM.resize(m);
    for(int i = 0; i < n; i++)
    {
        cin >> str_masN[i];
    }
    for(int i = 0; i < m; i++)
    {
        cin >> str_masM[i];
    }
 
    for(int i = 0; i < m; i++)
    {
        int size  = str_masM[i].size();
        const char * buf = str_masM[i].c_str();
        for(int j = 1; j <= size; j++)
        {
            int nn = 0;
            for(int k = 0; k < n; k++)
            {
                if(str_masN[k].find(buf, 0, j) == 0)
                    nn++;
            }
            if(nn == 0)
            {
                for(int l = 0; l < size - j + 1; l++) cout << 0 << ' ';
                break;
            }
            cout << nn << ' ';
        }
        cout << endl;
    }
    return 0;
}
но на одной проверяющей системе практически на последнем тесте он выпоняется на 164 мс болше положенного.
Помогите пожалуста оптмизировать код

Добавлено через 1 час 11 минут


Добавлено через 37 минут
up up

Добавлено через 55 минут
Блин, ребят, помагите пожалуста

Добавлено через 32 минуты
up up up

Добавлено через 34 минуты
ААА пожалуста!!!

Добавлено через 2 часа 19 минут
UP!!!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.12.2010, 17:38     Оптимизация алгоритма
Посмотрите здесь:

Оптимизация алгоритма - C++
Всем привет. Если кто-то сможет оптимизировать &quot;это&quot;, то я отблагодарю его материально. uint32_t a0 = ps*26 + ps*51 + ps*102 + ps*51 +...

Оптимизация алгоритма - C++
#include&lt;iostream&gt; #include&lt;stdlib.h&gt; #include&lt;time.h&gt; #include&lt;iomanip&gt; using namespace std; #define jaba for(i=0; i&lt;k; i++)...

Оптимизация алгоритма - C++
Условие: Дана выборка (X_i, Y_i)_{i=1}^N. Предполагается, что она была построена по следующему закону: \begin{cases} Y=\beta \xi...

Оптимизация - C++
Мне нужно на определенную часть программы дать указание компилятору не оптимизировать эту часть. Может кто знает как это сделать???? ...

Оптимизация кода - C++
В общем дело такое, мне нужно 2 одинаковые программы(небольшие), только одна программа должна быть неоптимизированная, а другая, точно...

Оптимизация памяти - C++
Доброго времени суток. У меня есть класс(код показывать не буду, он не нужен), в приватном поле есть переменная типа int *, то есть класс...

Оптимизация функции - C++
Здравствуйте, каким образом(кроме switch) можно оптимизировать эту функцию(Нужен самый оптимизированный вариант): void blabla() { ...

Оптимизация программы на С++ - C++
Помогите оптимизировать программу на С++, я не представляю, что в ней можно изменить. Хотя бы намек на функцию, в которой нужна...

оптимизация кода - C++
Добрый вечер всем. У меня такая проблема: написал прогу, необходимо продемонстрировать ее работу. Т.е. есть L2 список, дек и массив деков,...

Оптимизация программы - C++
#include&lt;std_lib_facilities.h&gt; #include&lt;conio.h&gt; void moveHorse(int &amp;, int , int , int, int &amp;, int &amp;, int &amp;);//переставляет коня ...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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