LeetCode: Substring with concatenation of all words (http://leetcode.com/onlinejudge#question_30)

substring.cpp

/*
 * This is a very cool method to perform the leetcode task.
 * It is time O(n) (n being the size of string S) if it is
 * implemented with an unordered_map on line 65, otherwise it
 * is O(n*log(m)) (m being the size of the vector L)
 *
 * This method demonstrates how hashes can be used for 
 * comparison instead of strings. It is inspired by
 * the topcoder article: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching
 */


#include <vector>
#include <map>
#include <string>
#include <iostream>

using namespace std;

class Substring {
    private:
        int base,
            prime;

        //Will return the correct mod, even if a is negative
        int int_mod(int a, int b) {
            return (a%b + b)%b;
        }

        //Needed for the rolling has, it is the chosen numeral to the power of m-1
        int baseM_1(int m) {
            int base_1 = 1;
            for (int i=0; i < m; i++) {
                base_1 = int_mod(base_1*base, prime);
            }
            return base_1;
        }

        //Implements a rolling hash: See http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching
        int rollingHash(const string& input, int lastPos, int currentPos, int currentHash, int baseM_1) {
            if (lastPos >= 0) {
                currentHash = int_mod(currentHash - int_mod(input[lastPos]*baseM_1, prime), prime);
            }

            currentHash = int_mod(currentHash*base, prime);
            currentHash = int_mod(currentHash + input[currentPos], prime);
            return currentHash;
        }

    public:
        Substring() :
            base(26), //base is chosen as the size of my alphabet (in this case, latin alphabet lowercase = 26)
            prime(6291469) //a largish prime number for hashing (found from here: http://planetmath.org/goodhashtableprimes)
        {};

        vector<int> findSubstring(string S, vector<string> &L) {
            int stringHashCurrent = 0,
                stringHashBehind = 0,
                substringHash = 0,
                m = L[0].size(),
                lSize = m*L.size(),
                bm_1 = baseM_1(m-1),
                index = 0;

            map<int, bool> substringHashPresent;
            vector<int> substring(m,0),
                        substringSize(m,0);
            vector<int> indices;

            //Build a hash for each substring
            for (int i=0; i < L.size(); i++) {
                int tempSubstringHash = 0;
                for (int j=0; j < m; j++) {
                    tempSubstringHash = rollingHash(L[i], -1, j, tempSubstringHash, bm_1);
                }
                substringHashPresent[tempSubstringHash] = true;
                substringHash = int_mod(substringHash + tempSubstringHash, prime);
            }

            //Try Compare That Hash To Each Substring
            for (int i=0; i < S.size(); i++) {
                stringHashCurrent = rollingHash(S, ((i < m) ? -1 : i -m), i, stringHashCurrent, bm_1);
                if (i < m-1)
                    continue;
                index = i%m;

                if (i >= lSize) {
                    stringHashBehind = rollingHash(S, ((i-lSize-m < 0) ? -1 : i-lSize-m), i-lSize, stringHashBehind, bm_1);
                }

                if (substringHashPresent[stringHashCurrent]) {
                    int tempHash = int_mod(substring[index]+stringHashCurrent, prime);
                    substringSize[index] += m;

                    if (substringSize[index] > lSize) {
                        tempHash = int_mod(tempHash - stringHashBehind, prime);
                    }

                    if (tempHash == substringHash) {
                        indices.push_back(i-(lSize-1));
                    }

                    substring[index] = tempHash;
                } else {
                    substringSize[index] = 0;
                    substring[index] = 0;
                }
            }

            return indices;
        }
};