# Questions tagged [longest-common-substring]

The tag has no usage guidance.

12 questions
Filter by
Sorted by
Tagged with
2k views

### Longest common substring in linear time

We know that the longest common substring of two strings can be found in $\mathcal O(N^2)$ time complexity. Can a solution be found in only linear time?
38 views

### Longest common sequence matrix giving wrong answer

I am trying to find longest common sequence for these two strings SHINCHAN NOHARAAA The common sequence is NHA of length 3 ...
70 views

### Get count of longest zigzag sub-sequences

I know how to get longest zigzag sub-sequence and length of it. There are several methods available for that. But some times there are many sub-sequences available which have same length. How to ...
71 views

### Longest common subsequence with at most one swap

Is there a good algorithm for calculating the longest common subsequence where we consider two sequences identical if they can be transformed to one another with at most 1 swapping of subsequences (i....
132 views

### Number of optimal solutions for Longest Common Subsequence (Substring) problem

The Longest Common Subsequence (or Substring) problem (LCS) asks, given two strings $s_1$ and $s_2$, to find one string which is substring both of $s_1$ and $s_2$ and it is of maximum length. Each ...
175 views

### Probabilistic Substring Match

I'm looking for an algorithm that will help me determine substring matches at scale. I have a pool of 100+ million "needles" (strings). I can do as much pre-processing on them as I want, and storage ...
77 views

### Search String Algorithm in Table

For a given database table: ...