String Puzzle

[Sidoh]

I guess it's also worth noting that this could be done just as easily with a two dimensional array, haha.

You could cut down on the space usage a bunch if you used buckets for the nodes in the hash table, but it would increase the running time a bit (it'd still be O(n), though).

[iago]

Personally, I like the short, simple solution. Mine works perfectly in the least amount of code!

[Sidoh]

Personally, I like the short, simple solution. Mine works perfectly in the least amount of code!

I really did think about using a hash code similar to yours, but I decided against it since the problem specification very clearly said the input was alphanumeric.  I wanted to minimize the amount of space used.  I think some other solutions I saw (after doing mine, of course) were using buckets in their hash tables and they had size ~100.  That's definitely not very safe, though.

By the way, you're supposed to output the number of times the pairs occur.

[iago]

By the way, you're supposed to output the number of times the pairs occur.

I disagree based on the problem's wording:

I was asked that you have a string say, "foobarfoo", in which "fo" and "oo" are repeated twice. You have to find all such repeated pairs in O(n) time. The string can only have alphanumeric elements in it and code it in C.

It says to find all cases where they're repeated twice, then says "all such repeated pairs" -- I took that to mean that it wants cases where the pair of letters is repeated twice. It says nothing about outputting the number of times, but I took the "all such pairs" to mean that it only wants cases where there are two.

[Sidoh]

This was posted on another forum where the premise is interview questions.  I think I remember the poster clarifying that this was one of the requirements of the solution.  It doesn't matter, though.

Here's a paper on DAWGs.  It's pretty interesting.

http://www.primes.colostate.edu/Workshops/Networks/McConnell.pdf