http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dataStructures maybe good :-?

Do you know hashing on strings? It's not same as hashtable and essential to solve problems you mentioned.

I don't think you need a hash-table itself; it's already implemented in most common programming languages anyways. You just want to be able to use simple hashing.

The whole idea behind hashing strings is that you convert a string (slow comparison function) into an integer, and instead of comparing the whole strings for equality, you just compare their hashes. Classic polynomial hash is the most common:

where $p$ and M are suitably chosen numbers; for me, M = 10⁹ + 9 and p = 999983 (largest prime below 10⁶) work well.

All you need to be able to do is compute a hash (using classic modular arithmetic) and compare hashes instead of whole strings.

As a comment, both mentioned problems can be solved without hashing strings under given constraints. And you might prefer solutions not involving hashing in order to avoid arguing later whether it is a good practice to add anti-hash tests to test suite.

I found this paper useful to learn hashing http://www.mii.lt/olympiads_in_informatics/pdf/INFOL119.pdf

here you can find a good tutorial e-maxx site

here is my code for this question which i submitted while ago 4917199 . u just need a base and a prime. In this problem single hashing worked well but in several cases double hashing may be required. Second question is totally different from this one. In the hashing I used for first problem, it pre-computes in O(n^2) and answer each substring in O(1) but in second One n = 1e6. There is a way to hash an string by O(n) and answer each substring by O(1) by using partial sum. For each position i in string, u have to find biggest value for x such as hash(substr(i,x)) == hash(substr(0,x)). you can binary search on x. This will work in O(nlgn)