Skip to main content

Questions tagged [longest-common-substring]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
48 views

Can I speed up this multi-LCSS (Longest Common Substring) algorithm?

I'm creating a plagiarism detection algorithm in Python, which scores how much of document A has been plagiarised in document B, and returns all the copied sections in B that were plagiarised from A. ...
dben's user avatar
  • 11
0 votes
0 answers
13 views

Flowgarithm for common child program for a beginner (without pointers)

I'm a first year BCA student. Can you help me with flowgarithm of the common child problem (LCS) without pointers
Anandhakrishnan's user avatar
0 votes
0 answers
38 views

Could Radix Sort be used to tackle LCS algorithm?

Could one use the Radix Sort to find the Longest Common Subsequence problem? I am new to algorithms and was wondering if the string was converted to a list and then one was able to apply Radix Sort ...
EnlightenedFunky's user avatar
0 votes
0 answers
47 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 ...
Vk1's user avatar
  • 118
2 votes
1 answer
129 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 ...
Daigo's user avatar
  • 21
1 vote
0 answers
33 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 ...
Gunther Schadow's user avatar
0 votes
0 answers
141 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)$, ...
George Verouchis's user avatar
1 vote
0 answers
95 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 ...
Sharingan's user avatar
3 votes
0 answers
192 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 ...
Philip Müller's user avatar
1 vote
1 answer
164 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,...
markeb's user avatar
  • 11
1 vote
1 answer
720 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.
user118909's user avatar
8 votes
2 answers
11k 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?
Manoharsinh Rana's user avatar
1 vote
1 answer
62 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 ...
Pawan Nogariya's user avatar
1 vote
1 answer
238 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 ...
Lakindu Akash's user avatar
1 vote
1 answer
182 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....
Nesa's user avatar
  • 111
0 votes
2 answers
219 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 ...
Nisba's user avatar
  • 176
2 votes
1 answer
359 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 ...
Scovetta's user avatar
  • 123
0 votes
1 answer
103 views

Search String Algorithm in Table

For a given database table: ...
Raven's user avatar
  • 109
4 votes
0 answers
600 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 ...
Nima's user avatar
  • 41
0 votes
2 answers
1k 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 $...
Mads Ohm Larsen's 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 ...
Nuwan Indika's 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 ...
Ivan's 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 ...
mrk's user avatar
  • 3,718