Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [longest-common-substring]

The tag has no usage guidance.

1
vote
1answer
42 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
38 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
57 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 ...
3
votes
1answer
110 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
69 views

Search String Algorithm in Table

For a given database table: ...
2
votes
0answers
264 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
415 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
1k 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 ...
5
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 ...