Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.67/18: Рейтинг темы: голосов - 18, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 25.02.2018
Сообщений: 5
1

Максимальное пересечение строк

04.06.2018, 11:57. Показов 3715. Ответов 2
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Пересечением строк называется любая подстрока ненулевой длины, которая есть в обеих строках. Максимальное пересечение строк - это пересечение строк с наибольшей длинной строки пересечения. Вам нужно найти максимальное пересечение двух строк.

Входные данные
Дано две непустые строки длинной до 5000 символов. В строках используются только строчные английские буквы.

Выходные данные
Вывести максимальное пересечение двух строк. Если таких пересечений несколько, то вывести любое из них. Гарантируется, что есть хотя бы одно такое пересечение.

Стандартный ввод
abbaak
zbaazbbaak


Вывод: bbaak

Ограничение по времени: 1 с.
Ограничение по памяти: 64 МБ
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.06.2018, 11:57
Ответы с готовыми решениями:

Строка: Добавить в строковый класс функцию, которая создает строку, содержащую пересечение двух строк, то есть общие символы для двух строк.
Добавить в строковый класс функцию, которая создает строку, содержащую пересечение двух строк, то...

Пересечение строк матриц
Доброго времени суток :) Нужна помощь в составлении кусочка кода, который реализует пересечение...

Добавить в строковый класс функцию, которая создает строку, содержащую пересечение двух строк
Вот такое задание: Добавить в строковый класс функцию, которая создает строку, содержащую...

Пересечение двух прямых и проверка на пересечение
Доброго времени суток слизал функцию проверки отсюда:/segments_intersection_checking на всякий...

2
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
11.06.2018, 02:40 2
Прикольно. Я бы хеши пихал. Один мелкий. Другой ull
Итог. (5к)^2*log. Но если написать нормально - будет красиво.
Или простой дпшкой за квадрат.
0
838 / 641 / 940
Регистрация: 26.06.2015
Сообщений: 1,409
12.06.2018, 03:20 3
Лучший ответ Сообщение было отмечено KoEn99 как решение

Решение

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
47
48
49
50
51
52
53
#include <iostream>
#include <cstring>
 
template<typename T>
int find_seq(const T* a, int n1, const T* b, int n2, int& last){
    int* pa = new (std::nothrow) int[n2 + 1];
    if(pa == NULL)
        return -1;
 
    int* pb = new (std::nothrow) int[n2 + 1];
    if(pb == NULL){
        delete[] pa;
        return -1;
    }
    std::memset(pa, 0, (n2 + 1) * sizeof(int));
    std::memset(pb, 0, (n2 + 1) * sizeof(int));
 
    int* t, n, m = 0, index = -1;
    for(int i = n1 - 1; i >= 0; --i){
        for(int j = n2 - 1; j >= 0; --j){
            if(a[i] == b[j]){
                if((n = pa[j + 1] + 1) > m){
                    m     = n;
                    index = i;
                }
                pb[j] = n;
            } else
                pb[j] = 0;
        }
        t  = pa;
        pa = pb;
        pb = t;
    }
    delete[] pa;
    delete[] pb;
    last = index + m;
    return index;
}
 
int main(void){
    char s1[] = "abbaak";
    char s2[] = "zbaazbbaak";
 
    int last;
    int first = find_seq(s1, std::strlen(s1), s2, std::strlen(s2), last);
    if(first != -1){
        for(int i = first; i < last; ++i)
            std::cout << s1[i];
        std::cout << std::endl;
    }
    std::cin.get();
    return 0;
}
0
12.06.2018, 03:20
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.06.2018, 03:20
Помогаю со студенческими работами здесь

Двумерные массивы. Определить количество строк, максимальное из чисел
дана целочисленная прямоуголная матрица.Определить 1)количество строк , не содержащих ни одного...

Каким может быть максимальное число строк и столбцов матрицы
Здрасти, функция int** CreateMatrix(int count_row,int count_col) создает двумерный дин. массив, в...

Найти номер последней из ее строк,содержащих максимальное количество одинаковых элементов.
Дана целочисленная матрица M x N. Найти номер последней из ее строк,содержащих максимальное...

Определить, количество строк, не содержащих ни одного нулевого элемента, максимальное из чисел
Дана целочисленная прямоугольная матрица. Определить: 1) количество строк, не содержащих ни одного...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru