Submission 94c22b0b...

ChallengeString search
Submitter0xabcdef0db461f2f...
Submitted at2018-36-28
Gas used319499
/**
 * 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 haystack_bytes = bytes(haystack);
        bytes memory needle_bytes = bytes(needle);
        if (needle_bytes.length == 0) {
            return 0;
        }
        if (haystack_bytes.length < needle_bytes.length) {
            return -1;
        }
        if (needle_bytes.length == 1) {
            return find_one(haystack_bytes, needle_bytes);
        }
        return find_more(haystack_bytes, needle_bytes);
    }

    function find_one(bytes memory haystack_bytes, bytes memory needle_bytes)
    internal pure returns (int) {
        for (uint i = 0; i < haystack_bytes.length-needle_bytes.length+1; i++) {
            if (needle_bytes[0] == haystack_bytes[i]) {
                return int(i);
            }
        }
        return -1;
    }

    function find_more(bytes memory hsbytes, bytes memory nbytes)
    internal pure returns (int) {
        uint h = 0;
        uint n;
        while (h < hsbytes.length-nbytes.length+1) {
            if (hsbytes[h] != nbytes[0]) {
                h++;
            } else {
                if (hsbytes[h+nbytes.length-1] == nbytes[nbytes.length-1]) {
                    n = 1;
                    while (n < nbytes.length-1 && hsbytes[h+n] == nbytes[n]) {
                        n++;
                    }
                    if (n == nbytes.length-1) {
                        return int(h);
                    }
                }
                n = 0;
                while (n < nbytes.length && nbytes[n] != hsbytes[h+nbytes.length]) {
                    n++;
                }
                if (n == nbytes.length) {
                    h += nbytes.length;
                } else {
                    h += nbytes.length - n;
                }
            }
        }
        return -1;
    }
}