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

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

Восстановить пароль Регистрация
 
andrew_vorobey
0 / 0 / 0
Регистрация: 08.03.2013
Сообщений: 12
30.08.2013, 22:31     Наибольшая общая подстрока #1
Люди из раздела "алгоритмы" молчат.. спрошу тут..Прошу прощения за "флуд".
На днях отправил резюме в Яндекс. Откуда мне прислали задание-найти наибольшую общую подстроку. Строк не больше 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]);
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.08.2013, 22:31     Наибольшая общая подстрока
Посмотрите здесь:

C++ Подстрока
C++ наибольшая общая подпоследовательность
подстрока C++
подстрока С++ C++
Завершающая подстрока C++
Задача: плохая подстрока. Усовершенствовать алгоритм C++
Подстрока в пределах от M до N C++
Подстрока, заключенная в кавычки C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
30.08.2013, 23:18     Наибольшая общая подстрока #2
andrew_vorobey, Длина не больше 10000. Это значит 10000 символов. А кто будет считать символ конца строки, а? У тебя размер массива этого не учитывает.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
31.08.2013, 07:17     Наибольшая общая подстрока #3
я бы при таких ограничениях писал суф. автомат. Думаю, уровень Яндекса предполагает это, а не алгоритм из Википедии.
Yandex
Объявления
31.08.2013, 07:17     Наибольшая общая подстрока
Ответ Создать тему
Опции темы

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