Submission 2d7de93f...

ChallengeString search
Submitterwicketh.eth
Submitted at2018-07-09
Gas used172617
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
        uint256[256] memory badChar;
        uint256[] memory needle32 = new uint256[](nl);
        for (uint256 i = 0; i < nl; i++) {
            uint256 u32 = read1(needle, i);
            badChar[u32] = i + 1;
            needle32[i] = u32;
        }
        
        uint256 s = 0;
        while (s <= (hl - nl)) {
            i = nl - 1;
            while (i <= nl && needle32[i] == read1(haystack, s + i)) {
                i--;
            }
            if (i > nl) {
                return int256(s);
            } else {
                uint256 skip = i - badChar[read1(haystack, s + i)] - 1;
                
                if (skip > 1 && skip < hl) {
                    s += skip;
                } else {
                    s += 1;
                }
            }
        }
        return -1;
    }
    
    function read1(string memory a, uint256 i)
        private pure
        returns (uint8)
    {
        return uint8(bytes(a)[i]);
    }
}