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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Sergey_Chizhov
1 / 1 / 0
Регистрация: 21.09.2013
Сообщений: 30
26.01.2014, 12:22     Нахождение наибольшей общей подстроки! #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++ Дана матрица размера МхН.Найти номер ее строки с наибольшей суммой элементов и вывести данный номер, а также значение наибольшей суммы.
Задача поиска наибольшей общей подстроки C++
C++ Матрица. Найти номер ее ряда с наибольшей суммой элементов и вывести данный ее номер, а также значение наибольшей суммы
C++ В матрице размерностью MxN найти номер строки с наибольшей суммой элементов и вывести данный номер, а также значение наибольшей суммы
C++ Алгоритм поиска максимальной общей подстроки
Необходимо найти строку наибольшей длины и увеличить остальные строк в массиве к длине наибольшей строки, используя символ "!" C++
C++ Нужно найти строку наибольшей длины и увеличить остальные строк в массиве к длине наибольшей строки, используя символ "!"
C++ Нахождение наибольшей возрастающей подпоследовательности

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

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

Текущее время: 06:37. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru