Longest common subsequence

Summary

A longest common subsequence (LCS) is the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. The problem of computing longest common subsequences 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. Complexity For the general case of an arbit

Official source

https://en.wikipedia.org/wiki/Longest_common_subsequence

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (15)

Related publications

Related people

Related units

Related concepts (4)

Dynamic programming is both a mathematical optimization method and an algorithmic paradigm. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, fr

In computational linguistics and computer science, edit distance is a string metric, i.e. a way of quantifying how dissimilar two strings (e.g., words) are to one another, that is measured by countin

In computing, the utility diff is a data comparison tool that computes and displays the differences between the contents of files. Unlike edit distance notions used for other purposes, diff is line-o

Related concepts

Related courses (3)

Related courses

Related lectures (18)

Related lectures

Entity Search with NECESSITY

Nicolas Bonvin, Ekaterini Ioannou, Anshul Jain, Zoltán Miklós, Saket Sathe, Gleb Skobeltsyn

Loosely structured heterogeneous information spaces are typically created by merging data from a variety of different applications and information sources. A common problem these information spaces need to address is that various data describe the same real-word entities (e.g., conferences, organizations). In this demo, we introduce necessity, an efficient and scalable entity store. necessity is able to handle a large number of entities and at the same time provide an efficient and highly accurate entity search functionality for heterogeneous and partially structured queries that follow the vision of dataspaces.

2009

Learn to synthesize and synthesize to learn

Hazim Kemal Ekenel, Mohammad Saeed Rad, Jean-Philippe Thiran

Attribute guided face image synthesis aims to manipulate attributes on a face image. Most existing methods for image-to-image translation can either perform a fixed translation between any two image domains using a single attribute or require training data with the attributes of interest for each subject. Therefore, these methods could only train one specific model for each pair of image domains, which limits their ability in dealing with more than two domains. Another disadvantage of these methods is that they often suffer from the common problem of mode collapse that degrades the quality of the generated images. To overcome these shortcomings, we propose attribute guided face image generation method using a single model, which is capable to synthesize multiple photo-realistic face images conditioned on the attributes of interest. In addition, we adopt the proposed model to increase the realism of the simulated face images while preserving the face characteristics. Compared to existing models, synthetic face images generated by our method present a good photorealistic quality on several face datasets. Finally, we demonstrate that generated facial images can be used for synthetic data augmentation, and improve the performance of the classifier used for facial expression recognition.

ACADEMIC PRESS INC ELSEVIER SCIENCE2019

Learn to synthesize and synthesize to learn

Hazim Kemal Ekenel, Mohammad Saeed Rad, Jean-Philippe Thiran

2019