Описание тега longest-substring
Longest Substring is a classic computer science problem: given two strings, find the common strings, then return the string(s) in common with the greatest length.
1
ответ
Почему эта параллельная функция для вычисления самой длинной общей подпоследовательности медленнее, чем последовательная?
Параллельное вычисление LCS следует схеме волнового фронта. Вот параллельная функция, которая медленнее, чем последовательная реализация. (Я думаю, что количество диагоналей (параллельных) и количество рядов (последовательных) как-то связано с этим)…
14 ноя '12 в 00:14
3
ответа
Подход к самой длинной общей подстроке
В "Задаче программирования на общего ребенка" я использовал иной подход, чем общая проблема "Самая длинная общая подстрока". Кодекс #include <cmath> #include <cstdio> #include <vector> #include<string> #include <iostream&g…
20 дек '13 в 16:50
1
ответ
Суффиксный массив / суффиксное дерево с числами
Могут ли суффиксные деревья или суффиксные массивы эффективно использоваться с числами? Например: Можно ли использовать с массивом [1,2,3,4,5,3,9,8,5,3,9,8,6,4,5,3,9,11,9,8,7,11] извлечь все возможные непересекающиеся повторяющиеся подстроки всех ра…
21 янв '16 в 14:22
3
ответа
Самая длинная подпоследовательность со всеми вхождениями персонажа в 1 месте
В последовательности S из n символов; каждый символ может встречаться много раз в последовательности. Вы хотите найти самую длинную подпоследовательность S, где все вхождения одного и того же символа находятся вместе в одном месте; Например если S =…
19 ноя '12 в 20:00
8
ответов
Самая длинная общая подстрока без вырезания слова-питона
Учитывая следующее, я могу найти самую длинную общую подстроку: s1 = "this is a foo bar sentence ." s2 = "what the foo bar blah blah black sheep is doing ?" def longest_common_substring(s1, s2): m = [[0] * (1 + len(s2)) for i in xrange(1 + len(s1))]…
29 мар '14 в 02:15
5
ответов
Найдите самую длинную подстроку в алфавитном порядке. Что не так с моим кодом
Пока у меня есть: s = 'azcbobobegghakl' i = 0 j = 1 temp = '' #temporary variable I use to change longest longest = '' for b in range(len(s)): if s[i] <= s[j]: #checks if it's in alphabetical order temp+=s[i] if len(longest) < len(temp): longe…
06 июл '18 в 21:22
4
ответа
Самая длинная общая подстрока, ограниченная шаблоном
Проблема: У меня есть 3 строки s1, s2, s3. Каждый содержит мусорный текст с обеих сторон, с определяющим шаблоном в центре: text1+number1, number1 увеличивается на 2 в каждой строке. Я хочу извлечь text1+number1, Я уже написал код, чтобы найти numbe…
13 ноя '11 в 17:58
2
ответа
Самая длинная повторяющаяся подстрока с правильностью не менее k вхождений
Алгоритмы нахождения самой длинной повторяющейся подстроки формулируются следующим образом 1)build the suffix tree 2)find the deepest internal node with at least k leaf children Но я не могу понять, почему это работает, так что в основном, что делае…
15 ноя '16 в 14:58
2
ответа
Как найти самую длинную подстроку, которая встречается в каждом элементе массива?
У меня есть коллекция текстов от некоторых авторов. Каждый автор имеет уникальную подпись или ссылку, которая встречается во всех их текстах. Пример для Author1: $texts=['sdsadsad daSDA DDASd asd aSD Sd dA SD ASD sadasdasds sadasd @jhsad.sadas.com s…
13 окт '17 в 11:13
0
ответов
Использование самого длинного общего подстрокового решения для решения самой длинной палиндромной подстроки
Я пытался решить проблему самой длинной палиндромной подстроки, используя самую длинную общую подстроку, перевернув основную строку. Но мой алгоритм не работает на следующих примерах: "abadefdaba" ожидаемый результат: аба, но я получаю вывод как аба…
12 авг '18 в 12:39
1
ответ
Perl зацикливается в подпрограммах, чтобы отобразить самую длинную повторяющуюся строку, выбранную для определенного подраздела строки
Мне было интересно, если кто-нибудь знает, как упростить или обобщить этот код. Это дает правильный ответ, однако это применимо только к текущей ситуации. Мой код выглядит следующим образом: sub longestRepeat{ # list of argument @_ is: (sequence, nu…
14 ноя '13 в 02:32
1
ответ
Вывод самого длинного палиндрома в строке печатается правильно, несмотря на то, что он не является частью стека
Я написал некоторый код, чтобы найти самый длинный палиндром в строке (палиндром не должен появляться вместе, так как он может быть несмежным) Это работает почти во всех случаях. Для случая в коде ниже он также выводит правильный палиндром и его дли…
25 авг '15 в 10:56
2
ответа
Является ли этот метод самой длинной общей подстроки правильным?
Я нашел алгоритм для Longest Common Substring. Обычно это делается с помощью dynamic programmingс использованием двумерного массива размера mxn где m а также n являются длинами двух рассматриваемых строк. Я построю следующую матрицу для двух строк. …
27 фев '14 в 13:40
0
ответов
Нахождение макс. Общих подстрок в 2 строках с использованием хеша и бинарного поиска
Предположим, у меня есть 2 большие строки размером 10^5. Как я могу найти максимально общие подстроки из обеих строк со сложностью O(NlogN), используя Hash и Binary Search. Объяснение с кодом будет очень полезно:)
30 янв '18 в 07:51
10
ответов
Самая длинная общая подстрока из более чем двух строк - Python
Я ищу библиотеку Python для поиска самой длинной общей подстроки из набора строк. Есть два способа решения этой проблемы: используя суффикс деревья используя динамическое программирование. Реализованный метод не важен. Важно, что он может использова…
23 май '10 в 18:37
1
ответ
Ошибка сегментации в поиске самой длинной общей подпоследовательности
Постановка задачи: учитывая две строки a и b одинаковой длины, какая самая длинная строка (S) может быть построена так, что S является потомком a и b. Строка x называется дочерней по отношению к строке y, если x можно сформировать, удалив 0 или боле…
26 дек '14 в 13:40
1
ответ
Самая длинная общая подстрока в реализации 2 строк
Я пытаюсь реализовать самый длинный алгоритм общих подстрок в C, и после прочтения поста ниже, я действительно запутался в следующей части: Теперь самое большое значение LCP[2]=3, но оно для SA[1] и SA[2], оба из которых начинаются со строки A. Итак…
05 июл '13 в 22:15
1
ответ
Самая длинная общая подстрока без динамического программирования или суффиксного дерева
Руководство по разработке алгоритмов Skiena, вопрос 8-3, часть b, просит дать "более простой" алгоритм BigO(nm) для нахождения самой длинной общей подстроки, которая не зависит от динамического программирования. Очевидный ответ, по-видимому, заключа…
22 дек '17 в 23:58
2
ответа
Производительность Clojure - почему "уродливый" "трюк подкачки массивов" улучшает производительность lcs?
Это продолжение ответа @cgrand на вопрос "Эффективность Clojure для дорогих алгоритмов". Я изучал его и пытался применить некоторые из его приемов к моей экспериментальной настройке Clojure. Одна вещь, которая меня интересует, - это "уродливый" "трю…
11 июл '13 в 13:46
1
ответ
Найти самую длинную общую подстроку массива строк
В своем приложении Swift 3.0 я хочу определить лучшее имя для чего-либо, найдя самую длинную общую подстроку из 6-12 строк. Пример строки: ON/OFF office lights DIM office lights VALUE office lights FB office lights FB VALUE office lights Желаемый ре…
05 авг '17 в 17:56