# Questions tagged [subsequences]

Questions about algorithms related to subsequences, or about properties of subsequences.

23 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4k views

### Finding the longest repeating subsequence

Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ ...
260 views

### Polynomial time algorithm for finding a maximal monotone subset

Input: Some fixed $k>1$, vectors $x_i,y_i\in\mathbb R^k$ for $1\le i\le n$. Output: A subset $I\subset\{1,\dots,n\}$ of maximal size such that $(x_i-x_j)^T(y_i-y_j) \ge 0$ for all $i,j\in I$. ...
• 121
368 views

• 131
213 views

### Maximize interleaving subsequences two digit arrays/strings

Suppose I have two digit arrays, A and B as follows A = [3,4,5,6] B = [9,8,3] Now, I have ...
• 175
41 views

### How can I optimise a 8b10b encoding for maximum alignment?

Imagine you encode an 8 bit symbol as a 10 bit symbol that is sent sequentially over a wire. The goal at the receiver is to detect the byte boundary. Since there are 4 times more encoded symbols than ...
• 133
1 vote
23 views

### Find if union of discrete intervals with holes covers the whole interval space

There is a whole space interval [0,128] And several discrete sequences like: ...
1 vote
29 views

### Can suffix tree be used to match subsequences?

Given a set of strings, and a pattern - we want to compute the subset of those strings that have that pattern as a subsequence (not substring). Everything I've read of suffix trees refer to computing ...
1 vote
34 views

### Algorithm to identify rearrangements between two sequences of unique values

I have two sequences, seq1 and seq2, each consisting of unique values. Values can appear in seq1 or seq2 which do not appear in the other, and these values can appear in any order. How do I identify ...
• 111
1 vote
42 views

### How to build a set of closed chains with a sequence of different vertices?

I have a set of many bi-directional links like A-B, A-C, B-C, A-D, C-D, D-E, etc. I need to find a set of many closed chains with a sequence of different vertices (...
1 vote
139 views

### proving that local sequence alignment can be done in linear space

according to the Smith-Waterman setup, I have 2 string sequences S and T, and I want to identify their respective subsequences $\alpha$ and $\beta$ whose global alignment have maximum score over all ...
• 339
1 vote
259 views

### Find equal length subsequences with maximum difference of sums, for given maximum subsequence length

The problem is the following. Suppose we have a sequence of n non-negative numbers, each element with index i having its own ...
• 181
1 vote
874 views

### Longest Increasing Subsequence

I got no responses on stackoverflow, so I'm asking here: How useful is the LIS (Longest Increasing Subsequence) problem in tackling other CS problems? There are a few algorithms, using patience ...
• 1,891
1 vote
312 views

### DFA for strings with number of 0's odd only in substring longer than 1

I'm trying to design and DFA that accept string with an odd number of 0s, but counting only the ones within sub-strings with two or more 0. So, for example, 011000, will be accepted since it has 4 0...
• 121
28 views

### Is it possible to find Longest common subsequence of all pair of splits of a string in better than $O(n^3)$?

I have a string $a_0a_1..a_{n-1}$ Lets say we split the string at pos $i$, so the string are $a_0a_1....a_{i}$ and $a_{i+1}a_{i+2}....a_{n-1}$ Now I need to compute: \$max(LCS(a_0a_1....a_{i} , a_{i+1}...
86 views

### Competitive programming: Good Subsets problem

An array of length K is called good if for each subarray of the array, the sum of the subarray is not divisible by K+1. You are given an array A of length N. Find the number of subsequences of length ...
1k views

### Shortest Uncommon Subsequence

Here is another GeeksforGeeks problem that asks how to find the shortest Uncommon Subsequence of 2 strings? For example, Input : S = “babab” T = “babba” Output : 3The subsequence “aab” of ...
34 views

### How many optimal alignments can be there for a string of length m with a string of length n?

So I was practicing optimal alignment algorithm and I was stuck with this question of finding optimal alignment for a string of length m with a string length n ? Also is it possible to run it in theta(...