Rabin–Karp C solution


  • 0
    T

    Here is my Rabin–Karp C solution:

    int strStr(char* haystack, char* needle) {
        if (*haystack == '\0' && *needle == '\0') return 0;
        int requiredHash = 0;
        int highestMultiplier = 1;
        int needleLength = 0;
        char c;
        while(c = *(needle++)) {
            requiredHash = requiredHash * 31 + c;
            highestMultiplier *= 31;
            needleLength++;
        }
        int currentHash = 0;
        int i;
        // calculate the initial hash
        for (i = 0; i < needleLength; ++i) {
            if (haystack[i] == '\0') return -1;
            currentHash = currentHash * 31 + haystack[i];
        }
        for (i = 0; haystack[i + needleLength]; ++i) {
            if (currentHash == requiredHash) return i;
            currentHash = currentHash * 31 - highestMultiplier * haystack[i] + haystack[i + needleLength];
        }
        return currentHash == requiredHash ? i : -1;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.