Submission b6ee6c7d...

ChallengeString search
Submitterhyszeth.eth
Submitted at2018-30-26
Gas used103755
/**
 * This file is part of the 1st Solidity Gas Golfing Conshift.
 *
 * This work is licensed under Creative Commons Attribution ShareAlike 3.0.
 * https://creativecommons.org/licenses/by-sa/3.0/
 *
 * Author: Greg Hysen (@hysz)
 * Date: June 2018
 * Description: indexOf using Boyer-Moore algorithm w bad character heuristic.
 */

pragma solidity 0.4.24;

contract IndexOf {
    event E(int);
    /**
     * @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)
    {
        int256 haystackLength = int(bytes(haystack).length);
        int256 needleLength = int(bytes(needle).length);
        if(needleLength > haystackLength) return -1;
        if(needleLength == 0) return 0;
        if(needleLength == 1) {
            uint needleChar = uint(bytes(needle)[0]);
            for(uint idx = 0; idx < uint(haystackLength); idx++) {
                if(needleChar == uint(bytes(haystack)[idx])) return int256(idx);
            }
        }

        return indexOf(haystack, needle, haystackLength, needleLength);
    }

    function indexOf(string haystack, string needle, int256 haystackLength, int256 needleLength)
        public
        pure
        returns(int)
    {
        // Create badchar table
        int256[256] memory badchar;
        int i;
        while(i < needleLength) {
            badchar[uint(bytes(needle)[uint(i++)])] = i+1;
        }

        int maxNeedleIndex = needleLength-1;
        int256 haystackOffset;
        int maxHaystackOffset = (haystackLength - needleLength);
        uint last;
        int shift;
        int256 needleIndex;
        int tmp;
        while(true) {
            needleIndex = maxNeedleIndex;
            while(uint(bytes(needle)[uint(needleIndex)]) == (last = uint(bytes(haystack)[uint(haystackOffset + needleIndex)]))) {
                if(--needleIndex == -1) return haystackOffset;
            }

            // Handling each case individually saves ~10k gas.
            if((tmp = badchar[uint(last)]) != 0) {
                if((shift = needleIndex - tmp) > 2) {
                    if((haystackOffset += shift) > maxHaystackOffset) return -1;
                } else {
                    if(++haystackOffset > maxHaystackOffset) return -1;
                }
            } else {
                if(needleIndex > 0) {
                    if((haystackOffset += needleIndex + 2) > maxHaystackOffset) return -1;
                } else {
                    if(++haystackOffset > maxHaystackOffset) return -1;
                }
            }
        }
    }
}