Submission ee751cb1...

ChallengeString search
Submitter0xff3c2241cd767b7...
Submitted at2018-27-25
Gas used403367
/**
 * 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 {
    // supplied solution: 1467579
    // This solution: 466931 (Rabin–Karp_algorithm)

    // This equals function borrowed from implementation that was (accidentally?) supplied with
    // the original version of the source.
    function equals(string haystack, uint i, string needle) private pure returns(bool) {
        for(uint j = 0; j < bytes(needle).length; j++) {
            if(bytes(haystack)[i + j] != bytes(needle)[j]) {
                return false;
            }
        }
        return true;
    }

    /**
     * @dev Returns the index of the first occurrence of `needle` in `haystack`,
     *      or -1 if `needle` is not found in `haystack`.
     *
     * Input strings may be of any length <2^255.
     *
     * @param haystack The string to search.
     * @param needle The string to search for.
     * @return The index of `needle` in `haystack`, or -1 if not found.
     */
    function indexOf(string haystack, string needle) public pure returns(int) {
      uint m = bytes(needle).length;
      uint n = bytes(haystack).length;
      if (m > n){
        return -1;
      }
      uint hpattern;
      for (uint i = 0; i<m; i+=1){
        hpattern += uint(bytes(needle)[i]);
      }
      uint hs;
      for (i = 0; i<m; i+=1){
        hs += uint(bytes(haystack)[i]);
      }
      i=0;
      if (hs == hpattern){
        if (equals(haystack, i, needle)){
          return int(i);
        }
      }

      for (i = 1; i <= n-m; i++){
        hs -= uint(bytes(haystack)[i-1]);
        hs += uint(bytes(haystack)[i+m-1]);
        if (hs == hpattern){
          if (equals(haystack, i, needle)){
            return int(i);
          }
        }
      }
      return -1;
    }

}