Questions tagged [longest-common-substring]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
7
votes
2answers
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?
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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....
0
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
1answer
77 views

Search String Algorithm in Table

For a given database table: ...
3
votes
0answers
335 views

Does the Longest Common Subsequence problem reduce to its binary version?

I am working on a problem regarding the Longest Common Subsequence (LCS) of two strings, and I was wondering if there is any reduction from the general case of LCS to its binary version, i.e. by ...
0
votes
2answers
559 views

Longest substring with consecutive repetitions

I want to find the longest substring which is repeated without any gap between the repetitions. That is, given a string $x$, I want to find the longest $y$ such that $yy$ is a substring of $...
2
votes
1answer
2k views

How to find longest recurring pattern from lage string data set?

I need to find the substring that is from a 100,000 characters this substring must be most repeated and it need to be longest substring for example ...
1
vote
1answer
1k views

Which algorithm to use to find all common substring (LCS case) with really big strings

I'm looking for a particular case of longest common substring (LCS) problem. In my case I have two really big strings (tens or hundreds of milions byte characters) and need to find the LCS and other ...
6
votes
1answer
2k views

Find longest common substring using a rolling hash

The longest common substring (LCS) of two input strings $s,t$ is a common substring (in both of them) of maximum length. We can relax the constraints to generalize the problem: find a common substring ...