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

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

Восстановить пароль Регистрация
 
XXXaker
3 / 3 / 1
Регистрация: 30.06.2010
Сообщений: 43
05.12.2010, 17:38     Оптимизация алгоритма #1
Вот задачка:
Дана куча строк. Далее заданы запросы, представляющие собой некоторые строки. Для каждого префикса каждого запроса необходимо вывести количество строк в куче, которые имеют такое же начало, как и префикс запроса.

Входные данные: В первой строке содержится два целых числа 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++
оптимизация обмена C++
Оптимизация алгоритма вычисления определителя матрицы C++
Оптимизация алгоритма C++
Оптимизация алгоритма C++
Циклы и их оптимизация C++
Оптимизация программы C++
C++ Найти два элемента в массиве, разница между которыми максимальна (оптимизация алгоритма)

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

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

Текущее время: 15:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru