эээ, импер, зачем свой пост удалил, он же мне помог
ещё вопросик.
последний
Вот задача
Дана куча строк. Далее заданы запросы, представляющие собой некоторые строки. Для каждого префикса каждого запроса необходимо вывести количество строк в куче, которые имеют такое же начало, как и префикс запроса.
Входные данные: В первой строке содержится два целых числа N и М – количество строк в куче и количество запросов. (1 <= N, M <= 105). Далее записаны 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
|
вот мой код:
#include <iostream>
#include <string>
using namespace std;
string str_masN[100001], str_masM[100001];
int main()
{
int n, m;
cin >> n >> 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;
}
он абсолютно рабочий, но сцуко на 165 мс больше положенного времени выполняется
Как ещё его можно оптимизировать?