Submission e80a0148...

ChallengeString search
Submitter0x53b21be84eece2e...
Submitted at2018-08-24
Gas used421981
/**
 * 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.
     */

    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;
        if (needle_len > haystack_len) return -1;

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

        for (i = 0; i < needle_len; i++) {
            needle_hash = needle_hash * 389 + uint8(bneedle[i]);
            hay_hash = hay_hash * 389 + uint8(bhaystack[i]);
            haymult *= 389;
        }
        
        if ((back_hash * haymult + needle_hash) == hay_hash) {
            return int(i - needle_len);
        }

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

            back_hash *= 389;
            back_hash += uint8(bhaystack[i - needle_len]);
            if ((back_hash * haymult + needle_hash) == hay_hash) {
                return int(i - needle_len + 1);
            }
        }
        
        return -1;
    }
}