Submission 12bb0ac5...

ChallengeString search
Submitterwicketh.eth
Submitted at2018-38-09
Gas used105956
pragma solidity ^0.4.23;

contract IndexOf {
    
    /// @author Remco Bloemen <[email protected]>

    function indexOf(string haystack, string needle)
        public payable
        returns(int256)
    {
        uint256 hl = bytes(haystack).length;
        uint256 nl = bytes(needle).length;
        if(nl > hl) {
            return -1;
        }
        if(nl == 0) {
            return 0;
        }
        
        // Boyer–Moore–Horspool
        
        // Bad character rule
        uint256[256] memory badChar;
        uint256[] memory needle32 = new uint256[](nl);
        
        for (uint256 i = 0; i < nl; i++) {
            // Needle lookup table
            uint256 s = read1(needle, i);
            needle32[i] = s;
            
            // Bad character table
            if (i != nl - 1) {
                badChar[s] = i + 1;
            }
        }
        
        s = 0;
        while (s <= (hl - nl)) {
            i = nl - 1;
            
            uint256 hsn = read1(haystack, s + nl - 1);
            uint256 hsi = hsn;
            while (needle32[i] == hsi) {
                if(i == 0) {
                    return int256(s);
                } 
                i--;
                hsi = read1(haystack, s + i);
            }
            s += nl - badChar[hsn];
        }
        return -1;
    }
    
    function read1(string memory a, uint256 i)
        private pure
        returns (uint8)
    {
        return uint8(bytes(a)[i]);
    }
}