Submission 56d2f783...
/**
* 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/
*
* Author: Greg Hysen (@hysz)
* Date: June 2018
* Description: indexOf using Boyer-Moore algorithm w bad character heuristic.
*/
pragma solidity 0.4.24;
contract IndexOf {
event E(int);
/**
* @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) {
int256 haystackLength = int(bytes(haystack).length);
int256 needleLength = int(bytes(needle).length);
if(needleLength > haystackLength) return -1;
if(needleLength == 0) return 0;
int maxNeedleIndex = needleLength-1;
// Create badchar table
int256[256] memory badchar;
int i = 0;
while(i < needleLength) {
badchar[uint(bytes(needle)[uint(i++)])] = i;
}
//
int s = 0;
int maxS = (haystackLength - needleLength);
byte last;
int test;
int j = maxNeedleIndex;
while(true) {
if(bytes(needle)[uint(j)] == (last=bytes(haystack)[uint(s+j)])) {
j--;
if(j < 0) return s;
} else {
s += 1 > (test = j - badchar[uint(last)]) ? 1 : test;
if(s > maxS) return -1;
j = maxNeedleIndex;
}
}
}
}