Submission f3a234d3...

ChallengeString search
Submitter0x9e0ad99de20a444...
Submitted at2018-29-28
Gas used500742
/**
 * 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 {
    
    function indexOf(string haystack, string needle) public pure returns(int) {
        //v2.1
        uint haystackLen = bytes(haystack).length;
        uint needleLen = bytes(needle).length;
        bytes1 firstString;
        bytes1 secondString;
        if((haystackLen == 0) || (needleLen == 0)){
            return 0;
        }
        int[] memory needleVector = new int[](needleLen);
        needleVector[0] = -1;
        for(uint i = 1; i < needleLen;i++){
            int k = needleVector[i-1];
            while(k >= 0){
                firstString = bytes(needle)[uint(k)];
                secondString = bytes(needle)[i-1];
                if(secondString == firstString)
                    break;
                else
                    k = needleVector[uint(k)];
                needleVector[i] = k+1;
            }
        }
        
        i = 0;
        k = 0;
        while(i < haystackLen){
            if(k == -1){
                i++;
                k = 0;
                continue;
            }
            firstString = bytes(haystack)[i];
            secondString = bytes(needle)[uint(k)];
            if(secondString == firstString){
                i++;
                k++;
                if(uint(k) == needleLen)
                    return int(i-needleLen);
            }else
                k = needleVector[uint(k)];
        }
        return -1;
    }
}