About: Longest common subsequence problem

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Longest common subsequence problem Goto Sponge NotDistinct Permalink

An Entity of Type : dbo:Disease, within Data Space : el.dbpedia.org associated with source document(s)

The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring problem: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. The longest common subsequence problem is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in computational linguistics and bioinformatics. It is also widely used by revision control systems such as Git for reconciling multiple changes made to a revision-controlled collection of files.

Attributes	Values
rdf:type	Thing disease
rdfs:label	Longest common subsequence problem (en)
rdfs:comment	The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring problem: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. The longest common subsequence problem is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in computational linguistics and bioinformatics. It is also widely used by revision control systems such as Git for reconciling multiple changes made to a revision-controlled collection of files. (en)
differentFrom	Longest common substring problem
sameAs	Longest common subsequence problem Longest common subsequence problem
dbp:wikiPageUsesTemplate	dbt:Distinguish dbt:Harvtxt dbt:Main dbt:Reflist dbt:Short_description dbt:Unreferenced_section dbt:Wikibooks dbt:Strings
Subject	Combinatorics Dynamic programming Polynomial-time problems NP-complete problems Problems on strings
gold:hypernym	Problem
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Longest_common_subsequence_problem?oldid=1074260612&ns=0
Wikipage page ID	236105 (xsd:integer)
page length (characters) of wiki page	34459 (xsd:nonNegativeInteger)
Wikipage revision ID	1074260612 (xsd:integer)
Link from a Wikipage to another Wikipage	NP-hardness Version control Optimal substructure Backtracking Big O notation Rosalind (education platform) Overlapping subproblems Combinatorics Dynamic programming Polynomial-time problems Git NP-complete problems Diff Hirschberg's algorithm Method of Four Russians Quadratic growth Checksum Chvátal–Sankoff constants Hunt–Szymanski algorithm Computational linguistics Computer science Dynamic programming Edit distance Problems on strings File comparison Hash collision Hash function Tracy–Widom distribution Subsequence Longest alternating subsequence Longest common substring problem Longest increasing subsequence Memoization Merge (version control) Levenshtein distance Shortest common supersequence problem
has abstract	The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring problem: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. The longest common subsequence problem is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in computational linguistics and bioinformatics. It is also widely used by revision control systems such as Git for reconciling multiple changes made to a revision-controlled collection of files. For example, consider the sequences (ABCD) and (ACBAD). They have 5 length-2 common subsequences: (AB), (AC), (AD), (BD), and (CD); 2 length-3 common subsequences: (ABD) and (ACD); and no longer common subsequences. So (ABD) and (ACD) are their longest common subsequences. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
is differentFrom of	Longest common substring problem
is Wikipage redirect of	Lcs problem Difference Algorithm Longest-common subsequence problem Longest common subsequence LCS problem
is Link from a Wikipage to another Wikipage of	List of terms relating to algorithms and data structures Generalized suffix array Jaro–Winkler distance David Sankoff Diff Diff-Text DiffEngineX Hirschberg's algorithm Jewels of Stringology Chvátal–Sankoff constants Dan Hirschberg Hunt–Szymanski algorithm Dynamic programming Edit distance List of NP-complete problems List of algorithms File comparison Index of combinatorics articles Lcs problem LCS Longest alternating subsequence Longest increasing subsequence Levenshtein distance MUMmer Difference Algorithm Longest-common subsequence problem Longest common subsequence LCS problem
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (72 GB total memory, 1 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software