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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Текст и двумерный массив. http://www.cyberforum.ru/cpp-beginners/thread203673.html
Смысл такой: есть файл c текстом. Нужно его открыть, и каждое слово в отдельности перенести в свой элемент массива. (все динамическое). Подскажите как сделать грамотнее, мой вариант не работает,...
C++ Лаба по Символьной информации не знаю как решить вот этот вариант,остальные сделал,но этот не знаю( 5. Программа должна распознать символ, введенный пользователем, что это – цифра, знак или буква. Для букв программа должна... http://www.cyberforum.ru/cpp-beginners/thread203668.html
Произвести выравнивание по правому краю введенного текста C++
помогите пожалуйста!!!! срочно надо!! задача №1. Произвести выравнивание по правому краю введенного текста, для чего к каждой строке применить функцию WIDE(str,k), которая равномерно вставляет...
В массиве B(n) каждый элемент,кроме первого, заменить суммой всех предедущих элементов C++
Доброго времени суток,прошу помочь мне в решении нескольких задач. Задача № 1 В массиве B(n) каждый элемент,кроме первого, заменить суммой всех предедущих элементов Задача № 2 Дан двумерный...
C++ Местонахождение точки http://www.cyberforum.ru/cpp-beginners/thread203643.html
Ввести координаты (х,у) вершин многоугольника (за часовой стрелкой), и координаты отдельной точки. Найти место нахождение етой точки (Внутри многоугольника, снаружи, или на ребре). Язык С. Можна...
C++ Не получается разобраться Visual C++ Привет всем помогите пожалуйста кто может у меня такая проблема не могу решить задачи по C++ Работа со строками. В строке, содержащей последовательность слов, найти конец предложения,... подробнее

Показать сообщение отдельно
XXXaker
3 / 3 / 1
Регистрация: 30.06.2010
Сообщений: 43

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

05.12.2010, 17:38. Просмотров 362. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru