Submission def2f6bb...

ChallengeString search
Submitter0x53b21be84eece2e...
Submitted at2018-26-24
Gas used483532
/**
 * This file is part of the 1st Solidity Gas Golfing Contest.
 *
 * This work is licensed under Creative Commons Attribution ShareAlike 3.0.
 * https://creativecommons.org/licenses/by-sa/3.0/
 */

pragma solidity 0.4.24;

contract IndexOf {
    /**
     * @dev Returns the index of the first occurrence of `needle` in `haystack`,
     *      or -1 if `needle` is not found in `haystack`.
     *
     * Input strings may be of any length <2^255.
     *
     * @param haystack The string to search.
     * @param needle The string to search for.
     * @return The index of `needle` in `haystack`, or -1 if not found.
     */
     
    //  algorithm kmp_search:
    // input:
    //     an array of characters, S (the text to be searched)
    //     an array of characters, W (the word sought)
    // output:
    //     an array of integers, P (positions in S at which W is found)
    //     an integer, nP (number of positions)

    // define variables:
    //     an integer, j ← 0 (the position of the current character in S)
    //     an integer, k ← 0 (the position of the current character in W)
    //     an array of integers, T (the table, computed elsewhere)

    // let nP ← 0

    // while j < length(S) do
    //     if W[k] = S[j] then
    //         let j ← j + 1
    //         let k ← k + 1
    //         if k = length(W) then
    //             (occurrence found, if only first occurrence is needed, m may be returned here)
    //             let P[nP] ← j - k, nP ← nP + 1
    //             let k ← T[k] (T[length(W)] can't be -1)
    //     else
    //         let k ← T[k]
    //         if k < 0 then
    //             let j ← j + 1
    //             let k ← k + 1
    function indexOf(string haystack, string needle) public pure returns(int) {
        
        bytes memory bhaystack = bytes(haystack);
        bytes memory bneedle = bytes(needle);
        uint needle_len = bneedle.length;
        uint haystack_len = bhaystack.length;
        // uint[] memory hashmem = new uint[](haystack_len);
        if (needle_len > haystack_len) return -1;

        // uint memory hayhashes = new uint[](haystack_len);

        uint i;
        uint needle_hash = 0;
        uint haymult = 1;
        uint hay_hash = 0;
        uint back_hash = 0;

        // if (i > 0)
        //     hashmem[0] = 0;

        for (i = 0; i < needle_len; i++) {
            needle_hash *= 389;
            needle_hash += uint8(bneedle[i]);
            needle_hash %= 1000000007;
        }

        for (i = 0; i < needle_len; i++) {
            hay_hash *= 389;
            hay_hash += uint8(bhaystack[i]);
            hay_hash %= 1000000007;
            // hayhashes[i] = ;

            haymult *= 389;
            haymult %= 1000000007;
        }
        if ((back_hash * haymult + needle_hash) % 1000000007 == hay_hash) {
            return int(i - needle_len);
        }

        for (; i < haystack_len; i++) {
            hay_hash *= 389;
            hay_hash += uint8(bhaystack[i]);
            hay_hash %= 1000000007;

            back_hash *= 389;
            back_hash += uint8(bhaystack[i - needle_len]);
            back_hash %= 1000000007;

            if ((back_hash * haymult + needle_hash) % 1000000007 == hay_hash) {
                return int(i - needle_len + 1);
            }
        }
        
        return -1;
    }
}