Questions tagged [longest-common-substring]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
35 views

Disjoint $k$ Increasing Subsequences

Given a permutation $P$ and an integer $k$, we need to devise an algorithm which finds the $k$ disjoint increasing subsequences (say $L_1,L_2\ldots, L_k$) such that the sum total of their lengths (say ...
user avatar
  • 122
2 votes
1 answer
97 views

Efficiently find longest common substring for all substring pairs of S and T

I am trying to find the Gesalt similarity of a string $S$ and all substrings of $T$ using Gestalt Pattern Matching (Ratcliff Obershelp Algorithm) This algorithm requires me to find the matches of S ...
user avatar
  • 21
1 vote
0 answers
30 views

Has anyone seen the following string classifier discussed?

The closes related question I have found for this is Find string patterns preferably in regex for string streams, but it has no answer and is also a little less constrained as my idea. Given a set of ...
user avatar
0 votes
0 answers
50 views

How to find the LCP of string pairs in a set

I have a set of $k$ strings of $n$ length each. I need an algorithmic strategy that finds the LCP (Longest Common Prefix) of each set's string pair. In addition, I need time complexity $O(k*n+a)$, ...
user avatar
1 vote
0 answers
52 views

Longest palindrome after swapping operation

I know that Manacher's algorithm can be used to find the longest palindromic substring of a string in linear time. But I want to find the longest palindromic substring after swapping any two indices ...
user avatar
2 votes
0 answers
98 views

Intellij string search and highlight algorithm

I'm searching for an alogrithm that takes two strings, a query and a string that is to be searched for the query. The algorithm should result in a 'found' when the string contains the characters of ...
user avatar
1 vote
1 answer
115 views

Longest Common subsequence theorem in CLRS

In CLRS in the dynamic programming chapter, there is a theorem about the longest common subsequence prefix that states the following: Theorem Let the $X=(x_1,x_2,\dots,x_m)$ and $Y=(y_1,y_2,\dots,...
user avatar
  • 11
0 votes
1 answer
407 views

Can I find all the common subsequences between 2 sequences by using dynamic programming?

I need to know if there's a dynamic programming algorithm that returns all common subsequences between 2 sequences not just the longest one. Thank you.
user avatar
7 votes
2 answers
8k 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?
user avatar
1 vote
1 answer
49 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 ...
user avatar
1 vote
1 answer
174 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 ...
user avatar
1 vote
1 answer
129 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....
user avatar
  • 111
0 votes
2 answers
192 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 ...
user avatar
  • 176
2 votes
1 answer
293 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 ...
user avatar
  • 123
0 votes
1 answer
81 views

Search String Algorithm in Table

For a given database table: ...
user avatar
  • 109
4 votes
0 answers
563 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 ...
user avatar
  • 41
0 votes
2 answers
879 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 $...
user avatar
2 votes
1 answer
3k 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 ...
user avatar
1 vote
1 answer
2k 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 ...
user avatar
  • 121
7 votes
1 answer
3k 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 ...
user avatar
  • 3,610