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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Sergey_Chizhov
1 / 1 / 0
Регистрация: 21.09.2013
Сообщений: 30
#1

Нахождение наибольшей общей подстроки! - C++

26.01.2014, 12:22. Просмотров 1474. Ответов 1
Метки нет (Все метки)

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
54
55
56
57
58
59
60
/*
Найти наибольшую общую подстроку у всех строк. 
Всего k строк(1<=k<=10).
В каждой строке не более 10000 символов(маленькие латинские буквы).
Изначально вводится кол-во строк(k), далее сами строки.
 
Ограничения: ОЗУ<=512мб,
             время <= 1с
----------------------------------------------------------------------------
 
Алгоритм 1:
 Находим наименьшую строку и разбиваем её на всевозможные подстроки.
 Далее сравниваем подстроки, начиная с самых больших.
 Если находим общую подстоку у всех строк, то
 проверяем остальные подстроки с длинной 1-ой нашедшейся подстроки
 (если есть другие подстроки с такой же длинной, то это тоже ответ)
 выходим из цикла.
 ---------------------------------------------------------------------------
 
Алгоритм 2:
 Находим наименьшую строку.
 Начинаем сравнивать строки(с наименьшей) посимвольно.
 Как только находим общий символ для всех строк -> заносим в buffer_1.
 Ищем следующий за ним символ во всех строках, если находим -> добавляем в buffer_1.
 Если не находим следующий символ, то ищем следующий, если нашли -> записываем в buffer_2
 и т.д. пока не закончаться символы наименьшей строки.
 
 Далее сравниваем длину буфферов и выводим наибольший/наибольшии.
 
 
реализация 1-ого алгоритма
*/
 
#include "std_lib_facilities.h"
#include "string.h"
 
 
const int  MAX=10000;
 
int main()
{
    cout<<"Input kol-vo strok(1-10): ";
    int nrow;
    cin>>nrow;
    char** Mas = new char *[nrow];
    for (int i=0;i<nrow;i++) 
        Mas[i]=new char [MAX];
    cout<<"Input stroki:\n";
    int min_len=10000;
    for(int i=0; i<nrow; i++){
         cin>>Mas[i];
    //   if (strlen(Mas[i])<min_len) 
    //       min_len=srtlen(Mas[i]);
    }
    //cout<<min_len;
 
        
    keep_window_open();
    return 0;
}
Выскажите свои мысли по поводу лучшего решения(алгоритма), предложите свой.

Как найти длину наименьшей строки в данном массиве char???
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.01.2014, 12:22     Нахождение наибольшей общей подстроки!
Посмотрите здесь:

Задача поиска наибольшей общей подстроки - C++
Нужно написать вот эту программку на Си. Поясню допустим дано 2 строки из них нужно найти одинаковые слова и вывести слова которое имеет...

Алгоритм поиска максимальной общей подстроки - C++
Доброго времени суток. Подскажите, как можно реализовать наиболее простой алгоритм поиска максимальной общей подстроки для параллельных...

Поиск наибольшей общей подпоследовательности методом методом полного перебора - C++
Здравствуйте! Помогите пожалуйста с этим адом :wall: Нужно решить задачу о поиске наибольшей общей подпоследовательности методом...

Нахождение общей площади, образованной объединением прямоугольников - C++
Я встал в ступор. И заранее извиняюсь, что не послал тему в алгоритмы, потому что я ее не нашел. Я правда не понимаю как решить данную...

Нахождение наибольшей возрастающей подпоследовательности - C++
Создать два файла: последовательность.in, последовательность.out. В первом файле задается некоторая последовательность состоящая из целых...

Нахождение наибольшей возрастающей последовательности в матрице - C++
Помогите пожалуйста понять, почему код работает не совсем верно. Мне нужно написать код, который находит длину наибольшей возрастающей...

Нахождение слова наибольшей длины в строке - C++
Строка состоит из слов,разделенных одним или несколькими пробелами.Найдите слово наибольшей длины.

Матрица. Найти номер ее ряда с наибольшей суммой элементов и вывести данный ее номер, а также значение наибольшей суммы - C++
Дана матрица размерности M x N. Найти номер ее ряда з найбольшою суммой элементов и вивести даный ее номер а также значение ...

В матрице размерностью MxN найти номер строки с наибольшей суммой элементов и вывести данный номер, а также значение наибольшей суммы - C++
Данная матрица размерности M x N. Найти номер ее строки с наибольшей суммой элементов и вывести данный номер, а также значение наибольшей...

Нужно найти строку наибольшей длины и увеличить остальные строк в массиве к длине наибольшей строки, используя символ "!" - C++
Вводится массив строк символов. Необходимо найти строку наибольшей длины и увеличить остальные строк в массиве к длине наибольшей строки,...

Необходимо найти строку наибольшей длины и увеличить остальные строк в массиве к длине наибольшей строки, используя символ "!" - C++
Вводится массив строк символов. Необходимо найти строку наибольшей длины и увеличить остальные строк в массиве к длине наибольшей строки,...

Найти длину максимальной подстроки, такой что в этой подстроке не существует подстроки равной какой-то строке - C++
Не могу решить задачу, я понял саму задачу. Не могу написать код, помогите, плз! У Дроида-На2а есть строка S, и K строк ai. Ваша задача...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nick Alte
Эксперт С++
1608 / 1000 / 118
Регистрация: 27.09.2009
Сообщений: 1,931
Завершенные тесты: 1
26.01.2014, 12:38     Нахождение наибольшей общей подстроки! #2
Цитата Сообщение от Sergey_Chizhov Посмотреть сообщение
предложите свой
Предлагаю: находим две строки наименьшей длины, составляем список всех их общих подстрок, упорядоченный по убыванию длины, после чего идём по списку, проверяя наличие каждой подстроки во всех остальных исходных. Первая подстрока, удовлетворяющая этому условию, будет искомым результатом.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru