Наибольшая общая подпоследовательность

@Beginner12 · Регистрация: 11.03.2013

Я правда не знаю в том ли разделе я создал.
Надо определить наибольшую общую подпоследовательность. Код писать не надо. Я хотел бы узнать по какому принципу заполняется массив элементов и по какому принципу делается шаг. Если можно, объясните пожалуйста на этом примере.
1.fabcfbcdea
dabfaccaad

@~~loro~~ · 31.03.2013, 19:47

в данном примере их две fa и ab, как правило в таких задачах требуется найти длину наибольшей общей последовательности.

@alechka · 31.03.2013, 20:01

на псевдокоде будет что-то вида
void func (substing, количество символов с первого)
если есть во второй последовательности, то
{
if (больше чем текущая максимальная), максимальная = текущая
func(subring,n+1)
}

вторая функция скармливает ей подстроки первой, начиная с i'того элемента

@~~loro~~ · 31.03.2013, 20:04

alechka, неа..

@alechka · 31.03.2013, 20:06

Сообщение от loro

alechka, неа..

есть более красивый способ (я верю, должен быть, а то моё решение - в лоб)? рассказывайте, уже интересно ^^

Psilon · 31.03.2013, 20:35

Префикс-функция

@alechka · 31.03.2013, 21:16

Сообщение от Psilon

Префикс-функция

спасибо, буду знать!

@Beginner12 0 / 0 / 0 Регистрация: 11.03.2013 Сообщений: 36
		1
	Наибольшая общая подпоследовательность 31.03.2013, 17:43. Просмотров 1670. Ответов 6 Метки нет (Все метки) Я правда не знаю в том ли разделе я создал. Надо определить наибольшую общую подпоследовательность. Код писать не надо. Я хотел бы узнать по какому принципу заполняется массив элементов и по какому принципу делается шаг. Если можно, объясните пожалуйста на этом примере. 1.fabcfbcdea dabfaccaad 0

@~~loro~~ Заблокирован
	31.03.2013, 19:47	2
	в данном примере их две fa и ab, как правило в таких задачах требуется найти длину наибольшей общей последовательности. 1

@alechka 75 / 50 / 14 Регистрация: 28.03.2013 Сообщений: 175
	31.03.2013, 20:01	3
	на псевдокоде будет что-то вида void func (substing, количество символов с первого) если есть во второй последовательности, то { if (больше чем текущая максимальная), максимальная = текущая func(subring,n+1) } вторая функция скармливает ей подстроки первой, начиная с i'того элемента 1

@~~loro~~ Заблокирован
	31.03.2013, 20:04	4
	alechka, неа.. 0

@alechka 75 / 50 / 14 Регистрация: 28.03.2013 Сообщений: 175
	31.03.2013, 20:06	5
	Сообщение от loro alechka, неа.. есть более красивый способ (я верю, должен быть, а то моё решение - в лоб)? рассказывайте, уже интересно ^^ 0

Psilon Master of Orion 6079 / 4935 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	31.03.2013, 20:35	6
	Префикс-функция 0

@alechka 75 / 50 / 14 Регистрация: 28.03.2013 Сообщений: 175
	31.03.2013, 21:16	7
	Сообщение от Psilon Префикс-функция спасибо, буду знать! 0

Опции темы