Submission 9b970734...

ChallengeString search
Submitter0xff3c2241cd767b7...
Submitted at2018-26-24
Gas used451958
/**
 * 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 {

    // (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 = hash(needle, 0, m, 0);
      for (uint i = 0; i <= n-m; i++){
        uint hs = hash(haystack, i, i+m, hs);
        if (hs == hpattern){
          if (equals(haystack, i, needle)){
            return int(i);
          }
        }
      }
      return -1;
    }

    function hash(string s, uint from, uint to, uint prevHash) pure returns (uint res){
      // TODO: Haven't considered trade-off here between ease of calculation and
      // frequency of collisions (which cause a needless execution of equals);
      if (prevHash==0){
        for (uint i = from; i<to; i+=1){
          res += uint(bytes(s)[i]);
        }
      } else {
        res = prevHash;
        res += uint(bytes(s)[to-1]);
        res -= uint(bytes(s)[from-1]);
      }
    }
}