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

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

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

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

26.01.2014, 12:22. Просмотров 1350. Ответов 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++ В матрице размерностью MxN найти номер строки с наибольшей суммой элементов и вывести данный номер, а также значение наибольшей суммы
C++ Алгоритм поиска максимальной общей подстроки
Необходимо найти строку наибольшей длины и увеличить остальные строк в массиве к длине наибольшей строки, используя символ "!" C++
C++ Нужно найти строку наибольшей длины и увеличить остальные строк в массиве к длине наибольшей строки, используя символ "!"
C++ Нахождение наибольшей возрастающей подпоследовательности
C++ Нахождение общей площади, образованной объединением прямоугольников
Нахождение наибольшей возрастающей последовательности в матрице C++
Нахождение слова наибольшей длины в строке C++
Поиск наибольшей общей подпоследовательности методом методом полного перебора C++
Найти длину максимальной подстроки, такой что в этой подстроке не существует подстроки равной какой-то строке C++

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

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

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