# Submission 7c224bf6...

Challenge String search michaelsproul.eth 2018-06-07 331787
``````/**
* This file is part of the 1st Solidity Gas Golfing Contest.
*
*
* Implementation by Michael Sproul (https://sproul.xyz)
*/

pragma solidity 0.4.24;

contract IndexOf {
/**
* @dev Returns the index of the first occurrence of `needle` in `haystack`,
*
* Input strings may be of any length <2^255.
*
* @param haystack_s The string to search.
* @param needle_s The string to search for.
* @return The index of `needle` in `haystack`, or -1 if not found.
*/
function indexOf(string haystack_s, string needle_s) public pure returns (int) {
bytes memory haystack = bytes(haystack_s);
bytes memory needle = bytes(needle_s);
uint n = haystack.length;
uint m = needle.length;
uint i = m;
uint stop = n - m;
uint j;
bool matched;
uint x = 1;

if (n < m) {
return -1;
}

// Rabin-Karp algorithm
// Define our hash function as follows:
// hash(x) = sum(256^i * x_i) mod 101
// Treat the string as most-significant-byte first

uint needle_hash;
uint substring_hash;
for (; i > 0; i = j) {
j = i - 1;
needle_hash = addmod(needle_hash, x * uint(needle[j]), 101);
substring_hash = addmod(substring_hash, x * uint(haystack[j]), 101);
x = mulmod(256, x, 101);
}

// x now equals 256^m

for (; i < stop; i++) {
if (needle_hash == substring_hash) {
// Check that all the characters actually match
matched = true;
for (j = 0; j < m; j++) {
if (haystack[i + j] != needle[j]) {
matched = false;
break;
}
}

if (matched) {
return int(i);
}
}

// Else, update the hash for the next iteration
// 1. Move all characters up a position by multiplying by 256
// 2. Subtract the most significant char (position i) (add -256^m * char)
// 3. Add the next char
uint z = 256 * substring_hash + x * (303 - uint(haystack[i]));

substring_hash = addmod(z, uint(haystack[i + m]), 101);
}

// Check for a match once more on the way out
if (needle_hash == substring_hash) {
// Check that all the characters actually match
matched = true;
for (j = 0; j < m; j++) {
if (haystack[i + j] != needle[j]) {
matched = false;
break;
}
}

if (matched) {
return int(i);
}
}

return -1;
}
}
``````