Submission 7cdc0bfd...

ChallengeString search
Submitter0xabcdef0db461f2f...
Submitted at2018-14-02
Gas used304961
/**
 * 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 hsBytes = bytes(haystack);
        bytes memory nBytes = bytes(needle);
        if (nBytes.length == 0) {
            return 0;
        }
        if (hsBytes.length < nBytes.length) {
            return -1;
        }
        if (nBytes.length == 1) {
            return findOne(hsBytes, nBytes[0]);
        }
        return findMuch(hsBytes, nBytes);
    }

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

    function findMuch(bytes memory hsBytes, bytes memory nBytes) internal pure returns (int) {
        uint h = 0;
        uint hsLen = hsBytes.length;
        uint nLen = nBytes.length;
        while (h < hsLen-(nLen-1)) {
            if (hsBytes[h] != nBytes[0]) {
                h++;
            } else {
                uint n = nLen - 1;
                while (hsBytes[h+n] == nBytes[n]) {
                    n--;
                    if (n == 0) {
                        return int(h);
                    }
                }
                n = 0;
                while (n < nLen && nBytes[n] != hsBytes[h+nLen]) {
                    n++;
                }
                h += n == nLen ? nLen : nLen - n;
            }
        }
        return -1;
    }
}