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

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

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

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

05.12.2010, 17:38. Просмотров 357. Ответов 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!!!
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.12.2010, 17:38
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Оптимизация алгоритма (C++):

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

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

Оптимизация алгоритма вычисления определителя матрицы - C++
Здравствуйте! Написал я давеча программку, которая считает определитель. Только вот беда - он не считает определители матриц выше 10...

Оптимизация алгоритма перемножения двух матриц - C++
Здравствуйте, нужна помощь. Есть 2 матрицы, нужно их перемножить так, что бы алгоритм выполнялся со скорость O(n) и O(log(n))

Найти два элемента в массиве, разница между которыми максимальна (оптимизация алгоритма) - C++
Есть правильное решение задачи. Не проходит последние тесты по времени. Задачу я уже сдал, но вопрос остался открытым. Сигнатура функции...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.12.2010, 17:38
Привет! Вот еще темы с ответами:

Оптимизация алгоритма Хаффмана - C++
Сделал архиватор, но работает он запредельно долго ~ 30 мин на папку размером 50Mb(и это только упаковка). нужна помощь &quot;Гуру&quot; что бы...

Оптимизация - C++
Как-нибудь можно уменьшить размер кода, т.е. сократить количество строк данного кода: #include &lt;cmath&gt; #include &quot;windows.h&quot; ...

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

оптимизация - C++
какие 5 способов оптимизации?


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

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

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