Submission 836032bf...

Challenge	String search
Submitter	wicketh.eth
Submitted at	2018-30-09
Gas used	355838

pragma solidity ^0.4.23;

contract IndexOf {
    
    /// @author Remco Bloemen <[email protected]>
    
    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;
        }
        
        // Knuth-Morris-Pratt failure table
        uint256[] memory F = new uint256[](nl);
        for(uint i = 2; i < nl; i++) {
            uint256 j = F[i - 1];
            for (;;) {
                if(read1(needle, j) == read1(needle, i - 1)) { 
                    F[i] = j + 1;
                    break; 
                }
                if(j == 0) {
                    F[i] = 0;
                    break;
                }
                j = F[j];
            }
        }
        
        i = 0;
        j = 0;
        for (;;) {
            if(j == hl) {
                return -1;
            }
            if(read1(haystack, j) == read1(needle, i)) {
                i++;
                j++;
                if(i == nl) {
                    return int256(j - nl);
                }
            } else if(i > 0) {
                i = F[i];
            } else {
                j++;
            }
        }
    }
    
    function read1(string memory a, uint256 i)
        private pure
        returns (bytes32)
    {
        return bytes(a)[i];
    }
}