How to speed up calculation of length of longest common substring?

Posted by eSKay on Stack Overflow See other posts from Stack Overflow or by eSKay
Published on 2010-04-25T21:19:26Z Indexed on 2010/04/25 21:23 UTC
Read the original article Hit count: 501

Filed under:

algorithm

|

lcs

|

dynamic-programming

|

suffix-tree

|

c++

I have two very large strings and I am trying to find out their Longest Common Substring.

One way is using suffix trees (supposed to have a very good complexity, though a complex implementation), and the another is the dynamic programming method (both are mentioned on the Wikipedia page linked above).

Using dynamic programming $alt text$

The problem is that the dynamic programming method has a huge running time (complexity is O(n*m), where n and m are lengths of the two strings).

What I want to know (before jumping to implement suffix trees): Is it possible to speed up the algorithm if I only want to know the length of the common substring (and not the common substring itself)?

© Stack Overflow or respective owner

Related posts about algorithm

Jpeg Algorithm vs BMP Algorithm?

as seen on Super User - Search for 'Super User'
I'm just wonder, what the differences are between creating a BMP file algorithm and JPG file algorithm ? If you know the others images' format algorithm, please post them. Thanks. >>> More
word disambiguation algorithm (Lesk algorithm)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hii.. Can anybody help me to find an algorithm in Java code to find synonyms of a search word based on the context and I want to implement the algorithm with WordNet database. For example, "I am running a Java program". From the context, I want to find the synonyms for the word "running", but the… >>> More
Search algorithm (with a sort algorithm already implemented)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, Im doing a Java application and Im facing some doubts in which concerns performance. I have a PriorityQueue which guarantees me the element removed is the one with greater priority. That PriorityQueue has instances of class Event (which implements Comparable interface). Each Event is associated… >>> More
Is there any algorithm for finding LINES by PIXEL COLORS on picture?

as seen on Stack Overflow - Search for 'Stack Overflow'
So I have Image like this I want to get something like this (I hevent drawn all lines I want but I hope you can get my idea) I need algorithm for finding all straight lines on it by just reading colors of pixels. No hard math, no Haar, no Hough. Some algorithm which would be based on points… >>> More
collsion issues with quadtree [on hold]

as seen on Game Development - Search for 'Game Development'
So i implemented a Quad tree in Java for my 2D game and everything works fine except for when i run my collision detection algorithm, which checks if a object has hit another object and which side it hit.My problem is 80% of the time the collision algorithm works but sometimes the objects just go… >>> More

Related posts about lcs

How Can I Improve This Algorithm (LCS)

as seen on Stack Overflow - Search for 'Stack Overflow'
(define (lcs lst1 lst2) (define (except-last-pair list) (if (pair? (cdr list)) (cons (car list) (except-last-pair (cdr list))) '())) (define (car-last-pair list) (if (pair? (cdr list)) (car-last-pair (cdr list)) (car list))) (if (or (null? lst1) (null… >>> More
Debian - "WARNING: untrusted versions of the following packages will be installed!"

as seen on Server Fault - Search for 'Server Fault'
When i try to install or update any packages I get: Untrusted packages could compromise your system's security. You should only proceed with the installation if you are certain that this is what you want to do. I strongly suspect this is related to the error i get on update: $ sudo aptitude update Get:… >>> More
Longest Common Subsequence

as seen on Stack Overflow - Search for 'Stack Overflow'
Consider 2 sequences X[1..m] and Y[1..n]. The memoization algorithm would compute the LCS in time O(m*n). Is there any better algorithm to find out LCS wrt time? I guess memoization done diagonally can give us O(min(m,n)) time complexity. >>> More
How to speed up calculation of length of longest common substring?

as seen on Stack Overflow - Search for 'Stack Overflow'
I have two very large strings and I am trying to find out their Longest Common Substring. One way is using suffix trees (supposed to have a very good complexity, though a complex implementation), and the another is the dynamic programming method (both are mentioned on the Wikipedia page linked above)… >>> More
Can I use a plaintext diff algorithm for tracking XML changes?

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi all! Interesting question for you here. I'm working in Flex/AS3 on (for simplicity) an XML editor. I need to provide undo/redo functionality. Of course, one solution is to store the entire source text with each edit. However, to conserve memory, I'd like to store the diffs instead (these diffs… >>> More