Submission 4bb43eb7...

Challenge	String search
Submitter	hyszeth.eth
Submitted at	2018-26-30
Gas used	81914

/**
 * 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);


    int256 constant NOT_FOUND = -1;
    /**
     * @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)
    {
        uint256 haystackLength = bytes(haystack).length;
        uint256 needleLength = bytes(needle).length;
        if(needleLength > haystackLength) return -1;
        if(needleLength == 0) return 0;
        if(needleLength == 1) {
            uint needleChar = uint(bytes(needle)[0]);
            uint max = haystackLength/5 * 5;
            uint idx;
            while(idx != max) {
                if(needleChar == uint(bytes(haystack)[idx++])) return int256(--idx);
                if(needleChar == uint(bytes(haystack)[idx++])) return int256(--idx);
                if(needleChar == uint(bytes(haystack)[idx++])) return int256(--idx);
                if(needleChar == uint(bytes(haystack)[idx++])) return int256(--idx);
                if(needleChar == uint(bytes(haystack)[idx++])) return int256(--idx);
            }
            while(idx != haystackLength) if(needleChar == uint(bytes(haystack)[idx++])) return int256(--idx);
            return NOT_FOUND;
        }

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

    function indexOf(string haystack, string needle, uint256 haystackLength, uint256 needleLength)
        internal
        pure
        returns(int)
    {
        // Create badchar table
        uint256[256] memory badchar;
        uint tmp = needleLength/5 * 5;
        uint i;
        while(i != tmp) {
            badchar[uint(bytes(needle)[uint(i++)])] = uint(i+1);
            badchar[uint(bytes(needle)[uint(i++)])] = uint(i+1);
            badchar[uint(bytes(needle)[uint(i++)])] = uint(i+1);
            badchar[uint(bytes(needle)[uint(i++)])] = uint(i+1);
            badchar[uint(bytes(needle)[uint(i++)])] = uint(i+1);
        }
        while(i != needleLength) badchar[uint(bytes(needle)[uint(i++)])] = uint(i+1);

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

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