🔒 Locked

Finding the Longest String ... ?

Started by KulSeran Apr 16, 2004 at 1:24 AM 3 replies 450+ views

Original Post

Apr 16, 2004 at 1:24 AM

I was wondering if anyone knows a fast way of finding the longest repeated string in a buffer. "1234123412341234" has "1234" repeated 4 times, and so "12341234" is the longest string in the buffer "12341234abcd12341234" still has "12341234" as the longest string. i suspect that there is something faster than looking at every single letter, and seeing if the longest string exists between it and every other letter. this takes N^2 time.... far too slow if there is a big buffer.

LizardCPP

Apr 16, 2004 at 1:36 AM

There is a known dynamic programming problem called "Longest common subsequnce". Search for it on google.

LizardCPP

Desert Fox

Apr 16, 2004 at 2:51 AM

Look up the Boyer-Moore substring matching algorithm and the Suffix Search algorithm. The Suffix Search will be the fastest (I believe), but it will also eat up a very large amount of memory for very long starting strings.

civguy

Apr 16, 2004 at 3:24 AM

quote:
Original post by KulSeran
i suspect that there is something faster than looking
at every single letter, and seeing if the longest string
exists between it and every other letter.
this takes N^2 time.... far too slow if there is
a big buffer.

That enumerates O(N^2) substrings and for each substring sees if the substring is elsewhere. I believe it takes O(N^3) time.

KulSeran

Apr 16, 2004 at 12:08 PM

Thanks for the input.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.