Submission 562106f4...

Challenge	String search
Submitter	wicketh.eth
Submitted at	2018-56-09
Gas used	287534

pragma solidity ^0.4.23;

contract IndexOf {
    
    /// @author Remco Bloemen <[email protected]>
    
    //uint256 constant p1 = 0xed6d961a586550c76591d3943b3c6f76b621934aa7ffad3360fac1cf4aa0473f;
    uint256 constant p1 = 257;

    function indexOf(string haystack, string needle)
        public pure
        returns(int256)
    {
        uint256 hl = bytes(haystack).length;
        uint256 nl = bytes(needle).length;
        if(nl > hl) {
            return -1;
        }
        if(nl == 0) {
            return 0;
        }
        
        // Rabin-Karp without verify
        uint256 needleHash = 0;
        for(uint i = 0; i < nl; i++) {
            needleHash *= p1;
            needleHash += read1(needle, i);
        }
        uint256 factor = p1 ** (nl - 1);
        
        uint256 hayHash = 0;
        for(i = 0; i < nl; i++) {
            hayHash *= p1;
            hayHash += read1(haystack, i);
        }
        if (hayHash == needleHash) {
            return 0;
        }
        for (; i < hl; i++) {
            hayHash -= read1(haystack, i - nl) * factor;
            hayHash *= p1;
            hayHash += read1(haystack, i);
            if (hayHash == needleHash) {
                return int256(i - nl + 1);
            }
        }
        return -1;
    }
    
    function read1(string memory a, uint256 i)
        private pure
        returns (uint8)
    {
        return uint8(bytes(a)[i]);
    }
}