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

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

Войти
Регистрация
Восстановить пароль
 
andrew_vorobey
0 / 0 / 0
Регистрация: 08.03.2013
Сообщений: 12
#1

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

30.08.2013, 22:31. Просмотров 818. Ответов 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]);
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.08.2013, 22:31     Наибольшая общая подстрока
Посмотрите здесь:

Подстрока - C++
Всем Приветы, вопрос на сейчас такой: Как получить подстроку из данной строки, если данная задаётся пользователем? Вот пример: ...

подстрока - C++
в заданной строке найти позицию первого вхождения указанной подстроки .не используя стандартные функции.спасибо!

Подстрока в пределах от M до N - C++
помогите пож преобразовать в с++,за ранее спасибо Var i,m,n:byte; a,b:string; begin write('Введите слово'); ...

Завершающая подстрока - C++
Есть параметр std:::string Text и локальная переменная i, хранящая индекс символа. Требуется удалить из параметра начальные символы по этот...

Подстрока, заключенная в кавычки - C++
Всем добрый день! Вот такая примерно задачка. Имеется string S1=&quot;This is the long string having some words \&quot;in quotes\&quot;&quot;; Надо...

Задача: плохая подстрока. Усовершенствовать алгоритм - C++
Задача: Найдите, сколько существует строк заданной длины n, состоящих только из символов 'a', 'b' и &quot;c&quot;, и не содержащих подстроки...

Наибольшая длина отрезка - C++
Дан массив целых чисел. Рассмотреть отрезки последовательности (подпоследовательности идущих подряд членов), состоящие из одинаковых...

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

Определить позицию, с которой подстрока входит в строку - C++
не работает программа, выдает ошибки помогите плз // Лабораторная работа №3 // Массивы // #include &quot;stdafx.h&quot; #include...

Посчитать, сколько раз подстрока встречается в строке - C++
здравствуйте всем. хочу посчитать сколько раз подстрока встречается в строке и не получается) помогите пожалуйста)подскажите что не так? ...

Наибольшая возрастающая подпоследовательность за O(NlogN) - C++
Здравствуйте! Вот тут написал код НВП за О(NlogN).Но на тестирующей системе он выдает на тесты некоторые неправильные ответы.Тестов я...

Наибольшая средняя линия треугольника - C++
Составить программу, которая вычисляет наибольшую среднюю линию треугольника с заданными координатами вершин...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dani
1300 / 637 / 56
Регистрация: 11.08.2011
Сообщений: 2,280
Записей в блоге: 2
Завершенные тесты: 1
30.08.2013, 23:18     Наибольшая общая подстрока #2
andrew_vorobey, Длина не больше 10000. Это значит 10000 символов. А кто будет считать символ конца строки, а? У тебя размер массива этого не учитывает.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
31.08.2013, 07:17     Наибольшая общая подстрока #3
я бы при таких ограничениях писал суф. автомат. Думаю, уровень Яндекса предполагает это, а не алгоритм из Википедии.
Ответ Создать тему
Опции темы

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