Submission 91ce109f...

ChallengeString search
Submittersggc.yuetloo.eth
Submitted at2018-27-30
Gas used159135
/**
 * 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;

        int shift = 0;
        int shiftRoom = int(haystackLength - needleLength);

        // Search by naive algorithm when the needle is short
        // to avoid the expensive shift offset lookup table
        if( needleLength < 3 ) {
           while(shift <= shiftRoom) {
              int j = int(needleLength-1);
              while( j >= 0 && bytes(needle)[uint(j)] ==  bytes(haystack)[uint(shift+j)])
                 j--;
   
              if( j < 0 ) 
                 return shift; // found it
              
              shift++;
           }
           return -1;
        }

        // Search by Bayer-Moore bad character algorithm
        // https://www.geeksforgeeks.org/pattern-searching-set-7-boyer-moore-algorithm-bad-character-heuristic/

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

        shift = 0;
        while(shift <= shiftRoom) {
           j = int(needleLength-1);
           while( j >= 0 && bytes(needle)[uint(j)] ==  bytes(haystack)[uint(shift+j)])
              j--;

           if( j < 0 ) 
              return shift; // found it
           
           int shiftOffset = j - (offset[uint(bytes(haystack)[uint(shift+j)])] -1);
           shift += ( 1 > shiftOffset? 1 : shiftOffset);
        }
        return -1;
    }
}