Submission 3c3545c2...

ChallengeString search
Submitterhyszeth.eth
Submitted at2018-39-06
Gas used195070
/**
 * 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 {
    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) {
        // Boyer-Moore algorithm w bad character heuristic
        // https://www.geeksforgeeks.org/pattern-searching-set-7-boyer-moore-algorithm-bad-character-heuristic/
        int256 haystackLength = int(bytes(haystack).length);
        int256 needleLength = int(bytes(needle).length);
        int maxNeedleIndex = needleLength-1;
        if(needleLength > haystackLength) return -1;
        if(needleLength == 0) return 0;

        int256[256] memory badchar;
        for(int i = 0; i < needleLength; ++i) {
            badchar[uint(bytes(needle)[uint(i)])] = i+1;
        }

        int s = 0;
        int maxS = (haystackLength - needleLength);
        while(s <= maxS) {
            for(int j = maxNeedleIndex; j >= 0; j--) {
                byte last;
                if(bytes(needle)[uint(j)] != (last=bytes(haystack)[uint(s+j)])) {
                    int test = j - badchar[uint(last)] - 1;
                    s += 1 > test ? 1 : test;
                    break;
                }
            }
            if(j < 0) return s;
        }

        if(s > (haystackLength - needleLength)) return -1;
        return s;
    }
}