М
Молодежь
К
Компьютеры-и-электроника
Д
Дом-и-сад
С
Стиль-и-уход-за-собой
П
Праздники-и-традиции
Т
Транспорт
П
Путешествия
С
Семейная-жизнь
Ф
Философия-и-религия
Б
Без категории
М
Мир-работы
Х
Хобби-и-рукоделие
И
Искусство-и-развлечения
В
Взаимоотношения
З
Здоровье
К
Кулинария-и-гостеприимство
Ф
Финансы-и-бизнес
П
Питомцы-и-животные
О
Образование
О
Образование-и-коммуникации
lizavetabelkin
lizavetabelkin
13.09.2022 02:50 •  Информатика

Объясните мне кратко ход решения (код писать не нужно). с информатикса, номер - 3871. строка s называется для строки t, если t начинается с s и заканчивается на s. например, «abra» является для строки «abracadabra». в частности, сама строка t является своим . играют важную роль в различных алгоритмах на строках. в этой требуется решить обратную о поиске , которая заключается в следующем. задан словарь, содержащий n слов t1, t2, …, tn и набор из m строк-образцов s1, s2, …, sm. необходимо для каждой строки-образца из заданного набора найти количество слов в словаре, для которых эта строка-образец является . требуется написать программу, которая по заданному числу n, n словам словаря t1, t2, …, tn, заданному числу m и m строкам-образцам s1, s2, …, sm вычислит для каждой строки-образца количество слов из словаря, для которых эта строка-образец является . входные данные первая строка входного файла содержит целое число n (1 ≤ n ≤ 200 000). последующие n строк содержат слова t1, t2, …, tn, по одному слову в каждой строке. каждое слово состоит из строчных букв латинского алфавита. длина каждого слова не превышает 50. суммарная длина всех слов не превышает 106. словарь не содержит пустых слов. затем следует строка, содержащая целое число m (1 ≤ m ≤ 200 000). последующие m строк содержат строки-образцы s1, s2, …, sm, по одной на каждой строке. каждая строка-образец состоит из строчных букв латинского алфавита: длина каждой строки-образца не превышает 50. суммарная длина всех строк-образцов не превышает 106. никакая строка-образец не является пустой строкой. выходные данные выходной файл должен содержать m чисел, по одному на строке. для каждой строки-образца в порядке, в котором они заданы во входном файле, следу.т вывести количество слов словаря, для которых она является . примеры входные данные 4 abacaba abracadabra aa abra 3 a abra abac выходные данные 4 2 0 решать надо через

👇
Ответ:
mot1475
mot1475
13.09.2022
Можно поступить следующим образом: создаем multimap. Читаем слова из словаря, для каждого слова находим все супрефиксы, вставляем их в multimap в качестве ключа, значение можно ставить любое (например, (int) 1). После этого в цикле читаем слова-образцы и выводим значение count от каждого слова-образца. 

Программа будет иметь примерно такую структуру:
multimap<string, ...> subprefixes
input n
n times:
    input s
    for j = 0..size of s:
        if s[..j] is subprefix of s:
            subprefixes.insert(pair<string, ...>(s[..j], ...))
input m
m times:
    input s
    print subprefixes.count(s)

Остался вопрос, как определять, является ли s[..j] супрефиксом.  Конечно, можно это делать наивно: пройти циклом для всех возможных длин подстрок j и проверить, правда ли, что s[0] = s[s.size() - j - 1], s[1] = s[s.size() - j]...

Как можно ускорить всё это?
1) Выберем какое-нибудь достаточно большое (по сравнению с кодами символов) простое число x, например, x = 1009. Вычислим для строки s все хеши по формуле h_n(s)=s_0+s_1x+s_2x^2+\dots+s_{n-1}x^{n-1} для n = 1..len s (это делается за линейное время относительно len s, если предпросчитать все степени x от нулевой до 50)
Теперь если у строки s длины k есть супрефикс длины j, то обязательно h_j(s)x^{k-j}=h_{k}(s)-h_{k-j-1}(s) – проверить это быстрее, чем ходить циклом.
2) Необязательно хранить в multimap-е подстроки, это дорого и по времени и по памяти. Можно хранить хеши.
3) Можно вместо одного multimap-а создать 50 multimap-ов, в каждом хранить только супрефиксы одной длины.

Получаем примерно такое:
pow = new long long[51]
pow[0] = 1
for i = 1..50:
    pow[i] = x * pow[i - 1]
suprefixes = new multimap<long long, ...>[51]
input n
n times:
    input s
    h = hashes(s)
    k = len s
    for j = 1..k:
         if h[j] * pow[k - j] == h[k] - h[k - j - 1]:
              suprefixes[j].insert(pair(h[j], ...))
input m
m times:
    input s
    print puprefixes[len s].count(hash(s))

В принципе, для такого решения multimap не нужен, достаточно иметь map, и хранить для каждого ключа количество вхождений. Это можно делать и для multimap.
4,8(24 оценок)
Открыть все ответы
Ответ:
Grechk
Grechk
13.09.2022

#include <iostream>

int main() {

const int SIZE = 10;

bool isSence = false;

int sum = 0;

int count = 0;

int arr[SIZE];

for (int i = 0; i < SIZE; i++)

{

 arr[i] = rand() % 20 - 10; // "рандомно" заполняем массив от -10 до 10

 std::cout << arr[i] << "\t"; // выводим массив в консоль

 if (arr[i] >= 0)

  isSence = true;

}

for (int i = 0; i < SIZE; i++)

{

 if ((isSence) && (arr[i] > 0))

  sum += arr[i]; //sum = sum + arr[i];

  count++;

}

if (isSence)

 std::cout << "\nсреднее арифметическое положительных чисел = " << double(sum) / count << std::endl; // явное приведение типов

else

 std::cout << "\nВ массиве нету положительных чисел или нету нулей и/или отрицательных чисел" << std::endl;

return 0;

}

4,4(24 оценок)
Ответ:
krasorka
krasorka
13.09.2022
Только программа, блок-схему не знаю
#include <iostream>
#include <iomanip>
#include <vector>
#include <ctime>
int main()
{
    using namespace std;

    const int n = 5;
    int A[n][n];
    int D[n][n];
    vector<int> B(n);
    vector<int> C(n);
    vector<int> S(n);   //результирующий вектор

    //как-нибудь заполняем исходные матрицы и вектора
    srand(time(0));
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            A[i][j] = rand() % (n * n) - n * n / 2;
            D[i][j] = rand() % (n * n) - n * 2;
        }
        B[i] = rand() % (n * n) - n;
        C[i] = rand() % (n * n) - n * n + n;
    }

    //выведем исходные данные на экран
    cout << "matrix A:\n";
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
            cout << setw(5) << A[i][j];
        cout << endl;
    }

    cout << "\nmatrix D:\n";
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
            cout << setw(5) << D[i][j];
        cout << endl;
    }

    cout << "\nvector B:\n";
    for (int i = 0; i < n; ++i)
        cout << setw(5) << B[i] << endl;

    cout << "\nvector C:\n";
    for (int i = 0; i < n; ++i)
        cout << setw(5) << C[i] << endl;

    //вычислим требуемое
    for (int i = 0; i < n; ++i)
    {
        S[i] = 0;
        for (int j = 0; j < n; ++j)
            S[i] += D[i][j] * C[j];
        S[i] += 3 * B[i];
    }

    //выведем результат на экран
    cout << "\nvector S = D * C + 3 * B:\n";
    for (int i = 0; i < n; ++i)
        cout << setw(5) << S[i] << endl;

    return 0;
}
4,7(45 оценок)
Новые ответы от MOGZ: Информатика
logo
Вход Регистрация
Что ты хочешь узнать?
Спроси Mozg
Открыть лучший ответ