Submission 99bc06c3...

ChallengeString search
Submitter0x53b21be84eece2e...
Submitted at2018-55-30
Gas used90577
/**
 * 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.
     */

//       1685  undefined
//       2075  undefined
//       4475  undefined
//       5020  undefined
//      18604  undefined
//      18638  undefined
//       2678  Test with needle longer than haystack
//     103372  Pathological worst case for anything using a naive nested loop implementation
//     333717  Long needle
// Total gas for IndexOf: 490264

    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;
        if (needle_len == 0) return 0;
        if (needle_len == 1) {
            needle_hash = uint(bneedle[0]);
            for (i = 0; i < haystack_len; i++) {
                if (uint(bhaystack[i]) == needle_hash) return int(i);
            }
            return -1;
        }

        for (i = 0; i < needle_len; i++) {
            needle_hash |= 1 << uint(bneedle[i]);
        }
        uint needlelast = uint(bneedle[needle_len - 1]);
        for (i = needle_len - 1; i < haystack_len; i++) {
            uint haybyte = uint(bhaystack[i]);
            if (needle_hash & (1 << haybyte) == 0) {
                i += needle_len - 1;
            }
            else if (needlelast == haybyte) {
                for (uint j = i - 1; j + needle_len > i; j--) {
                    // i - 1 + needle_len - i - 1
                    // needle_len - 2
                    // j = i + 1 - needle_len
                    if (bhaystack[j] != bneedle[j + needle_len - i - 1] ) {
                        break;
                    }
                }
                if (j + needle_len == i) {
                    return int(j + 1);
                }
            }
        }

        return -1;

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

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

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