{"id":2867,"date":"2009-03-10T11:49:00","date_gmt":"2009-03-10T17:49:00","guid":{"rendered":"http:\/\/www.lordandrei.com\/blog\/?p=2867"},"modified":"2009-03-10T11:49:00","modified_gmt":"2009-03-10T17:49:00","slug":"algorithm-note","status":"publish","type":"post","link":"http:\/\/www.lordandrei.com\/blog\/2009\/03\/10\/algorithm-note\/","title":{"rendered":"Algorithm note"},"content":{"rendered":"

I saw a post on one of my coding boards talking about a solution for an ‘interview-style’ problem.<\/p>\n

The issue was to find the longest common substring.<\/p>\n

What this means is: Given the word “abracadabra” you are looking for the longest repeated set of characters.<\/p>\n

The longest repeated sub-string is “abra” which appears at positions 0 and 7 (counting from 0).<\/p>\n

The solution the person presented involved putting the strings from smallest to largest into a dictionary (hash table) with counts of iterations.
\na-4
\nb-2
\nab-2<\/p>\n

And then walking the tree to find the largest result. This solution seems odd to me.<\/p>\n

My solution is to make a dynamic array that can be queried for contents. Further, doing it from longest to shortest:<\/p>\n

Edit<\/b> gwenix<\/a> points out a string can’t be repeated until it’s no more than half the length. So start from longest string (len \/2) rounded down.
\nEnd Edit<\/b><\/p>\n

Solution:
\nGet longest string: abracadabra<\/i>
\nIs string in array? YES? got answer and bail; No –> add to array
\n*Reduce look string by 1 character
\nMove to start of target string:
\n**Get look string: abracadabr<\/i>
\nIs string in array? YES? got answer and bail; No –> add to array
\nIs look string at end of target string? Yes –> loop back to *; No –> move forward one character and loop back to **<\/p>\n

This is massively not optimised for time or processing. But it’s a first stab.
\nAlso, just pseudo code… loop counters would be my next pass.<\/p>\n

Comments? Improvements?<\/p>\n

Share this:<\/h3>