Submission 5dbe306a...

ChallengeString search
Submittersggc.yuetloo.eth
Submitted at2018-08-28
Gas used315086
/**
 * This is a modified version of the original contract from
 *   https://github.com/arachnid/sggc.git
 * 
 * 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) {
        uint haystackLength = bytes(haystack).length;
        uint needleLength = bytes(needle).length;
        if(needleLength > haystackLength) {
            return -1;
        }
        if( needleLength == 0 ) return 0;

        // build a table for skipping past the length of needle
        // if the mismtached character is not found in the needle
        uint[] memory delta = new uint[](256);
        for( uint i =0; i < delta.length; i++ ) {
           delta[i] = needleLength;
        }
        for( i =0; i < needleLength-1; i++ ) {
           delta[uint(bytes(needle)[i])] = needleLength-1-i;
        }

        // do the pattern matching
        uint j=0;
        uint increment=1;
        for(i = needleLength-1; i < haystackLength; i=i+increment) {
           for( j=0; j <needleLength; j++ ) {
              
              if(bytes(needle)[needleLength-1-j] != bytes(haystack)[i-j]) {
                 increment=delta[uint(bytes(haystack)[i-j])];
                 break;
              }
           } 
           if( j == needleLength ) return int(i-(needleLength-1));
        }
    
        return -1;
    }
}