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

Наибольшая общая подстрока - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ с++ перегрузки http://www.cyberforum.ru/cpp-beginners/thread946120.html
Нужна помощь с реализацией кода(перегрузка добавления элемента в массив) Полная постановка задачи. АТД - множество с элементами типа char. дополнительно перегрузить следующие операции: + - добавить элемент в множество (типа Char + set); (не понимаю как сделать) + - объединение множеств; (сделал) == - проверка множеств на равенство; (сделал) #include "stdafx.h" #include <iostream>...
C++ Всеми любимый random() Здравствуйте. Проблема такая, мне необходимо вызывать рандом в программе несколько раз для генерации новых значений переменных. а именно: void RandomFunct() { x=1 + rand() % 100 +1; y=1 + rand() % 100 +1; } http://www.cyberforum.ru/cpp-beginners/thread946104.html
Непонятная ошибка. Несколько файлов C++
один header подключаем в другой(у которого есть .cpp файл) и возникает ошибка! play1.h struct card { int first; int second;
C++ Ошибка компиляции при включении #include <vector>
Есть контейнер, идентичный std::vector Его код в vvector_vbase.h Если не включать в code.cpp #include <vector> программа компилируется и выдает ожидаемый результат. //vvector_vbase.h // Принципы и практика использования C++ Глава 19 // Principles and Practice Using C++ Chapter 19 #include <iostream> #include <memory>
C++ const_cast для чего и как функционирует http://www.cyberforum.ru/cpp-beginners/thread946080.html
Дошел в свой книге (Дейтел) до const_cast, не могу понять смысла, т.к. там нагромождено не нужно кода в примере, в 5 раза больше самого примера, вот я сделал свой пример: const int var = 10; int *ptr = const_cast<int *>(&var); cout << "*ptr: " << *ptr << " ptr: " << ptr << endl; // 10 cout << "var: " << var << " &var: " << &var << endl; // 10 *ptr = 15;
C++ Скачивание html исходника Здравствуйте) Хочу попросить помощи в следующем: Есть интернет страница с полем ввода данных (номер) после ввода номера на странице (той же) выдается информация о введенном номере Хочу написать программу которая методом перебора будет сохранять информацию о номерах перебор и поиск в исходнике, думаю, осилю сам Хочу лишь знать как сохранять исходники через XCode Пробовал подключать Asio (оно... подробнее

Показать сообщение отдельно
andrew_vorobey
0 / 0 / 0
Регистрация: 08.03.2013
Сообщений: 12

Наибольшая общая подстрока - C++

30.08.2013, 22:31. Просмотров 796. Ответов 2
Метки (Все метки)

Люди из раздела "алгоритмы" молчат.. спрошу тут..Прошу прощения за "флуд".
На днях отправил резюме в Яндекс. Откуда мне прислали задание-найти наибольшую общую подстроку. Строк не больше 10, символов в 1 строке не больше 10 000.

Я взял наивный алгоритм. Реализовал реализовал его не совсем так, как в Википедии(эффективнее).

Все отлично, он прошел 14 тестов, везде укладывался в 1 секунду. Но на 15 тесте, Яндекс мне ответил-результат не верен.

Формат входных данных- С начала число строк, потом эти строки.

Не пойму, в чем дело..Яндекс пишет, что все тесты верны. Я искал сторонние решения, и они выдавали мне такой же результат, что и у меня.

Вот 2 решения, которые у меня получились-"bb" и "iq". ..как бы намекая, что iq не достаточно.

И все же.. Это провал в моей логики, или в Яндекс-тестах?

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// Яндекс B.cpp: определяет точку входа для консольного приложения.
//
 
//#include "stdafx.h"
#include <iostream>
#include <string.h>
#include <time.h>
 
using namespace std;
const int MAX=10000;
char** _strings=new char*[10];
int len;
 
char* GetLargestCommonSubstring( char* str1, char* str2 );
inline void readNomberSubstrings();
inline const char* getMaxSubstring();
 
int main()
{
readNomberSubstrings();
cout<< getMaxSubstring();
return 0;
}
 
void readNomberSubstrings()
{
cin>>len;
 
for(int i=0; i<len;i++)
_strings[i]=new char[MAX];
 
for(int i=0; i<len; i++)
cin>>_strings[i];
}
 
const char* getMaxSubstring()
{
char *maxSubstring=_strings[0];
//long T=clock();
for(int i=1; i < len; i++)
maxSubstring=GetLargestCommonSubstring(maxSubstring, _strings[i]);
//cout<<clock()-T<<endl;
return maxSubstring;
}
 
char* GetLargestCommonSubstring( char* str1, char* str2 ) {
 
int strLen2=strlen(str2);
const int solution_size = strLen2+ 1;
 
int *x=new int[solution_size]();
int *y= new int[solution_size]();
 
int **previous = &x;
int **current = &y;
 
int max_length = 0;
int result_index = 0;
 
int j;
int length;
int J=strLen2 - 1;
 
for(int i = strlen(str1) - 1; i >= 0; i--)
{
for(j = J; j >= 0; j--) 
{
if(str1[i] != str2[j]) 
(*current)[j] = 0;
else 
{
length = 1 + (*previous)[j + 1];
if (length > max_length)
{
max_length = length;
result_index = i;
}
 
(*current)[j] = length;
}
}
 
swap(previous, current);
}
str1[max_length+result_index]='\0';
return &(str1[result_index]);
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru