Longest common substring problem (original) (raw)
Hledání nejdelšího společného podslova je úloha z oboru matematické informatiky, jejíž podstatou je pro zadané řetězce najít jejich nejdelší společné podslovo. Na rozdíl od příbuzné úlohy hledání nejdelší společné podposloupnosti je tedy hledána posloupnost znaků souvislá v obou vstupech.
| Property | Value |
|---|---|
| dbo:abstract | Hledání nejdelšího společného podslova je úloha z oboru matematické informatiky, jejíž podstatou je pro zadané řetězce najít jejich nejdelší společné podslovo. Na rozdíl od příbuzné úlohy hledání nejdelší společné podposloupnosti je tedy hledána posloupnost znaků souvislá v obou vstupech. (cs) In computer science, the longest common substring problem is to find a longest string that is a substring of two or more strings. The problem may have multiple solutions.Applications include data deduplication and plagiarism detection. (en) En informatique, le problème de la plus longue sous-chaîne commune, à ne pas confondre avec celui de la plus longue sous-séquence commune, consiste à déterminer la (ou les) plus longue(s) chaîne(s) de caractères qui est sous-chaîne de deux chaînes de caractères. Ce problème se généralise à la recherche de la plus longue sous-chaîne commune à plus de deux chaînes de caractères. (fr) Najdłuższy wspólny podłańcuch (NWP, ang. longest common substring) danych dwóch ciągów X i Y – najdłuższy możliwy podciąg elementów leżących obok siebie w ciągach X i Y. Zbliżonym pojęciem jest najdłuższy wspólny podciąg, którego elementy mogą jednak być rozdzielone w ciągach X i Y przez inne elementy tych ciągów. (pl) Наибольшая общая подстрока (англ. longest common substring) — подстрока двух или более строк, имеющая максимальную длину. Формально, наибольшей общей подстрокой строк называется строка , которая удовлетворяет условию , операция обозначает что строка является (возможно несобственной) подстрокой строки . Решение задачи поиска наибольшей общей подстроки для двух строк и , длины которых и соответственно, заключается в заполнении таблицы размером по следующему правилу, принимая, что символы в строке нумеруются от единицы. Максимальное число в таблице это и есть длина наибольшей общей подстроки, сама подстрока: и . В таблице заполнены значения для строк SUBSEQUENCE и SUBEUENCS: SUBSEQUENCE 000000000000S 010010000000U 002000010000B 000300000000E 000001001001U 001000010000E 000001002001N 000000000300C 000000000040S 010010000000 Получаем наибольшую общую подстроку UENC. Сложность такого алгоритма составляет O(mn). (ru) Найдовший спільний підрядок (англ. longest common substring) — підрядок двох або більше рядків, що має максимальну довжину. Формально, найдовшим спільним підрядком рядків називається рядок , що задовольняє умові , операція позначає що рядок є (можливо невласним) підрядком рядка . Розв'язання задачі пошуку найдовшого спільного підрядка для двох рядків і , довжини яких і відповідно, полягає в заповненні таблиці розміром за наступним правилом, приймаючи, що символи в рядку нумеруються від одиниці. Максимальне число в таблиці це і є довжина найбільшого спільного підрядка, сам підрядок: и . У таблиці заповнені значення для рядків SUBSEQUENCE і SUBEUENCS: SUBSEQUENCE 000000000000S 010010000000U 002000010000B 000300000000E 000001001001U 001000010000E 000001002001N 000000000300C 000000000040S 010010000000 Отримуємо найдовший спільний підрядок UENC. Складність такого алгоритму становить O(mn). (uk) 在计算机科学中，最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的，而子串却必须是。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/LongestSubstring_svg.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.geeksforgeeks.org/suffix-tree-application-5-longest-common-substring-2/ http://www.emanueleferonato.com/2010/12/01/solving-the-longest-common-substring-problem-with-as3/ http://metacpan.org/module/String::LCSS_XS http://metacpan.org/module/Tree::Suffix http://nist.gov/dads/HTML/longestCommonSubstring.html |
| dbo:wikiPageID | 2167401 (xsd:integer) |
| dbo:wikiPageLength | 7671 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1091317052 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:N-gram dbc:Dynamic_programming dbr:Generalized_suffix_tree dbr:Lowest_common_ancestor dbr:Computer_science dbr:String_(computer_science) dbc:Articles_with_example_pseudocode dbr:Data_deduplication dbr:Dynamic_programming dbc:Problems_on_strings dbr:Big_O_notation dbr:Plagiarism_detection dbr:Longest_palindromic_substring dbr:Word_RAM dbr:Substring dbr:B:Algorithm_implementation/Strings/Longest_common_substring dbr:File:LongestSubstring_svg.svg dbr:File:Suffix_tree_ABAB_BABA_ABBA.svg |
| dbp:wikiPageUsesTemplate | dbt:Distinguish dbt:Wikibooks dbt:Strings |
| dcterms:subject | dbc:Dynamic_programming dbc:Articles_with_example_pseudocode dbc:Problems_on_strings |
| rdf:type | owl:Thing yago:Abstraction100002137 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Problem114410605 yago:State100024720 yago:WikicatProblemsOnStrings |
| rdfs:comment | Hledání nejdelšího společného podslova je úloha z oboru matematické informatiky, jejíž podstatou je pro zadané řetězce najít jejich nejdelší společné podslovo. Na rozdíl od příbuzné úlohy hledání nejdelší společné podposloupnosti je tedy hledána posloupnost znaků souvislá v obou vstupech. (cs) In computer science, the longest common substring problem is to find a longest string that is a substring of two or more strings. The problem may have multiple solutions.Applications include data deduplication and plagiarism detection. (en) En informatique, le problème de la plus longue sous-chaîne commune, à ne pas confondre avec celui de la plus longue sous-séquence commune, consiste à déterminer la (ou les) plus longue(s) chaîne(s) de caractères qui est sous-chaîne de deux chaînes de caractères. Ce problème se généralise à la recherche de la plus longue sous-chaîne commune à plus de deux chaînes de caractères. (fr) Najdłuższy wspólny podłańcuch (NWP, ang. longest common substring) danych dwóch ciągów X i Y – najdłuższy możliwy podciąg elementów leżących obok siebie w ciągach X i Y. Zbliżonym pojęciem jest najdłuższy wspólny podciąg, którego elementy mogą jednak być rozdzielone w ciągach X i Y przez inne elementy tych ciągów. (pl) 在计算机科学中，最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的，而子串却必须是。 (zh) Наибольшая общая подстрока (англ. longest common substring) — подстрока двух или более строк, имеющая максимальную длину. Формально, наибольшей общей подстрокой строк называется строка , которая удовлетворяет условию , операция обозначает что строка является (возможно несобственной) подстрокой строки . Решение задачи поиска наибольшей общей подстроки для двух строк и , длины которых и соответственно, заключается в заполнении таблицы размером по следующему правилу, принимая, что символы в строке нумеруются от единицы. и . В таблице заполнены значения для строк SUBSEQUENCE и SUBEUENCS: (ru) Найдовший спільний підрядок (англ. longest common substring) — підрядок двох або більше рядків, що має максимальну довжину. Формально, найдовшим спільним підрядком рядків називається рядок , що задовольняє умові , операція позначає що рядок є (можливо невласним) підрядком рядка . Розв'язання задачі пошуку найдовшого спільного підрядка для двох рядків і , довжини яких і відповідно, полягає в заповненні таблиці розміром за наступним правилом, приймаючи, що символи в рядку нумеруються від одиниці. Максимальне число в таблиці це і є довжина найбільшого спільного підрядка, сам підрядок: и . (uk) |
| rdfs:label | Hledání nejdelšího společného podslova (cs) Plus longue sous-chaîne commune (fr) Longest common substring problem (en) Najdłuższy wspólny podłańcuch (pl) Наибольшая общая подстрока (ru) Найдовший спільний підрядок (uk) 最长公共子串 (zh) |
| owl:differentFrom | dbr:Longest_common_subsequence_problem |
| owl:sameAs | freebase:Longest common substring problem yago-res:Longest common substring problem wikidata:Longest common substring problem dbpedia-cs:Longest common substring problem dbpedia-fa:Longest common substring problem dbpedia-fr:Longest common substring problem dbpedia-pl:Longest common substring problem dbpedia-ru:Longest common substring problem dbpedia-uk:Longest common substring problem dbpedia-vi:Longest common substring problem dbpedia-zh:Longest common substring problem https://global.dbpedia.org/id/rs7Z |
| prov:wasDerivedFrom | wikipedia-en:Longest_common_substring_problem?oldid=1091317052&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/LongestSubstring_svg.svg wiki-commons:Special:FilePath/Suffix_tree_ABAB_BABA_ABBA.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Longest_common_substring_problem |
| is dbo:wikiPageDisambiguates of | dbr:LCS |
| is dbo:wikiPageRedirects of | dbr:Longest_common_substring dbr:Longest-common_substring_problem dbr:Longest_common_subword |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:N-gram dbr:Alignment-free_sequence_analysis dbr:Longest_common_substring dbr:Suffix_automaton dbr:Suffix_tree dbr:Dynamic_programming dbr:Joan_Feigenbaum dbr:Longest_common_subsequence_problem dbr:LCS dbr:Substring dbr:Longest-common_substring_problem dbr:Longest_common_subword |
| is owl:differentFrom of | dbr:Longest_common_subsequence_problem |
| is foaf:primaryTopic of | wikipedia-en:Longest_common_substring_problem |
