Описание тега lcs
NoneLcs , или самая длинная общая подпоследовательность, представляет собой проблему при поисковой оптимизации: по двум строкам найти общую подпоследовательность в заданных строках с максимальной длиной. Задача может быть решена за полиномиальное время с использованием подхода динамического программирования.
1
ответ
Почему эта параллельная функция для вычисления самой длинной общей подпоследовательности медленнее, чем последовательная?
Параллельное вычисление LCS следует схеме волнового фронта. Вот параллельная функция, которая медленнее, чем последовательная реализация. (Я думаю, что количество диагоналей (параллельных) и количество рядов (последовательных) как-то связано с этим)…
14 ноя '12 в 00:14
3
ответа
Подход к самой длинной общей подстроке
В "Задаче программирования на общего ребенка" я использовал иной подход, чем общая проблема "Самая длинная общая подстрока". Кодекс #include <cmath> #include <cstdio> #include <vector> #include<string> #include <iostream&g…
20 дек '13 в 16:50
0
ответов
Обнаруживать структуры miRNA с помощью LCS
Если дана биологическая последовательность, моя задача состоит в том, чтобы обнаружить miRNA-подобную последовательность, используя алгоритм LCS (самая длинная общая подпоследовательность). например, ATACCAGACGTTATTTTTTTGAACGACCACATACATAGC дается ка…
22 май '18 в 23:20
1
ответ
Сообщите обо всех длинных общих подпоследовательностях (LCS) и их адаптивном расположении в двух строках
Я только что закончил программу, которая позволяет сообщать обо всех возможных LCS и местоположении двух строк соответственно. Тем не менее, результат теста не совсем правильно. Например, если две строки - "AACADBCDADCB" и "DCACDCBBDBAD", правильный…
26 ноя '13 в 03:38
2
ответа
Самая длинная общая подпоследовательность printdDiff
Просто быстрый вопрос о самом длинном алгоритме Common subsequence. Я выполнил ту часть, в которой вам нужно создать подпоследовательность, следующим образом: public int[][] lcsLength(char[] input1, char[] input2) { int[][] opt = new int[M][N]; for …
27 фев '13 в 14:11
4
ответа
Как я могу найти длину lcs между двумя большими строками
Я написал следующий код в C# для получения длины самой длинной общей подпоследовательности двух текстов, заданных использованием, но она не работает с большими строками. Не могли бы вы мне помочь. Я действительно смущен. public Form1() { InitializeC…
15 фев '14 в 12:34
3
ответа
Максимальная рекурсия в рекурсивной функции LCS
Я пытаюсь выполнить функцию LCS, которая использует рекурсию, чтобы дать мне количество позиций, которые действительны LCS, наряду с местом LCS, изображенным здесь: input: LCS("smile", "tile") output: [3, "##ile", "#ile"] Всякий раз, когда я пытаюсь…
19 сен '16 в 17:58
1
ответ
Как использовать ЛИС для решения 10635 УВА
Как выполнить сокращение от самой длинной общей подпоследовательности до O(nlog n) самой длинной возрастающей подпоследовательности для задачи 10635 uva. Мне нужна помощь относительно логики, которая будет применяться для решения проблемы.
23 май '12 в 16:05
1
ответ
Нахождение номера сравнения в LCS В динамическом программировании
#include<iostream> #include<string.h> int count=0; using namespace std; int max(int a,int b) { return (a>b)?a:b; } int lcs(char *x,char*y ,int m,int n) { int l[m+1][n+1]; int i,j; for( i=0;i<=m;i++) { for(j=0;j<=n;j++) { if(i==0…
15 окт '15 в 15:18
1
ответ
Самая длинная общая подпоследовательность из трех последовательностей типа int
Я пытаюсь решить самую длинную общую подпоследовательность из трех последовательностей int с использованием C++. проблема классическая Задача Для трех последовательностей A = (a1, a2, . . ., an), B = (b1, b2, . . ., bm) и C = (c1, c2, . . ., cl) най…
05 апр '17 в 20:17
1
ответ
Как решить LCS(Longest Common Subsequence) с условием пропуска
Я знаю общую проблему LCS и алгоритм. Это вот так: LCS(Xi, Yj) = [0 (i = 0 or j = 0) or LCS(Xi-1, Yj-1) + 1 (xi = yj) or max(LCS(Xi, Yj-1), LCS(Xi-1, Yj)) (xi != yj)] Но что, если мы добавим условие разрыва? Например: String A is cttauaucagu String …
08 окт '13 в 12:09
1
ответ
Самая длинная общая подстрока с использованием суффиксных автоматов
Я использовал для вычисления самой длинной общей подстроки, используя динамическое программирование O (m * n), дерево суффиксов O (m + n), массив суффиксов O(nlog^2 n) в соответствии с моими потребностями. Недавно я выучил Suffix Automaton, который …
16 мар '14 в 20:18
0
ответов
Алгоритм LCS с конкретными условиями
Итак, проблема в двух словах: Мне нужно выполнить "Longest Common Subsequence" на трассировке системных вызовов программы в режиме реального времени. Что мы делаем сейчас, так это то, что у нас есть набор из ~250 подписей, каждая из которых состоит …
10 дек '18 в 00:46
0
ответов
Вычислить расстояние редактирования между 2 очень большими строками
СЦЕНАРИЙ: Учитывая 2 входные строки, мне нужно найти минимальное количество удалений вставок и замен, необходимых для преобразования одной строки в другую. Строки представляют собой текст из 2 файлов. Сравнение должно быть сделано на уровне слов. Чт…
11 мар '16 в 13:06
1
ответ
Самый длинный общий ответ
Я пытаюсь написать рекурсивный алгоритм, который находит самую длинную общую подпоследовательность из двух списков, как описано в http://en.wikipedia.org/wiki/Longest_common_subsequence_problem Похоже, что рекурсия никогда не заканчивается, и я не м…
19 окт '13 в 22:33
2
ответа
Самая длинная общая последовательность подпоследовательностей
Какая самая длинная общая подпоследовательность для этих 2 строк {xaybadfeg, abcdefg}. Разве это не "абдег"? Я использую этот алгоритм (метод динамического программирования), чтобы найти решение. Он возвращает "АДЕГ" в качестве ответа. Мое понимание…
09 июл '16 в 19:44
0
ответов
Нахождение самой длинной общей подпоследовательности и определение различий в алфавите
Я пытаюсь решить эту проблему с Каттис. Задача состоит в том, чтобы найти, сколько букв должно быть вставлено в предоставленную строку (взятую из сканера) и определить, сколько букв должно быть вставлено, чтобы шаблон содержал подпоследовательность,…
16 авг '18 в 03:17
2
ответа
Различение множества текстов друг от друга для получения шаблона и данных (поиск общих подпоследовательностей)
Предположим, есть много текстов, о которых известно, что они сделаны из одного шаблона (например, много HTML-страниц, отрисованных из шаблона, подкрепленного данными из какой-либо базы данных). Очень простой пример: id:937 name=alice; id:28 name=bob…
11 окт '13 в 06:15
3
ответа
Самая длинная общая палиндромная подпоследовательность
Есть ли эффективный алгоритм, который считает длину самой длинной общей палиндромной подпоследовательности двух заданных строк? например: Строка 1. afbcdfca Строка 2. bcadfcgyfka LCPS равен 5, а строка LCPS равна afcfa,
04 сен '12 в 19:54
0
ответов
Найти самые длинные аудио общие подпоследовательности
В ближайшие дни я собираюсь получить набор аудиоданных для проекта машинного обучения в университете. Файлы, которые я собираюсь получить, бывают двух видов: один, который представляет собой исходную аудио-последовательность целиком, а другой, котор…
23 авг '18 в 14:09