Andrei Freeman (lordandrei) wrote,
Andrei Freeman

Algorithm note

I saw a post on one of my coding boards talking about a solution for an 'interview-style' problem.

The issue was to find the longest common substring.

What this means is: Given the word "abracadabra" you are looking for the longest repeated set of characters.

The longest repeated sub-string is "abra" which appears at positions 0 and 7 (counting from 0).

The solution the person presented involved putting the strings from smallest to largest into a dictionary (hash table) with counts of iterations.

And then walking the tree to find the largest result. This solution seems odd to me.

My solution is to make a dynamic array that can be queried for contents. Further, doing it from longest to shortest:

Edit gwenix 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.
End Edit

Get longest string: abracadabra
Is string in array? YES? got answer and bail; No --> add to array
*Reduce look string by 1 character
Move to start of target string:
**Get look string: abracadabr
Is string in array? YES? got answer and bail; No --> add to array
Is look string at end of target string? Yes --> loop back to *; No --> move forward one character and loop back to **

This is massively not optimised for time or processing. But it's a first stab.
Also, just pseudo code... loop counters would be my next pass.

Comments? Improvements?
Tags: algorithms, coding

  • Our post holiday ritual

    Originally published at Lord Andrei's Blog. Please leave any comments there. Even with religion as complex and personal as it is in our…

  • Politically Correct Greeting Card

    Please accept with no obligation, implied or implicit my best wishes for an environmentally conscious, socially responsible, low stress,…

  • Twas a week before New Year's...

    ...and all through the house, not a drip of water; no chance of a souse. It looks like the (less than promoted) NYE 08/09 celebration this year is…

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded