• Advertisement

Archived

This topic is now archived and is closed to further replies.

Finding the Longest String ... ?

This topic is 5031 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
There is a known dynamic programming problem called "Longest common subsequnce". Search for it on google.

LizardCPP

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

  • Advertisement