# Submission def2f6bb...

Challenge String search 0x53b21be84eece2e... 2018-26-24 483532
``````/**
* This file is part of the 1st Solidity Gas Golfing Contest.
*
*/

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 The string to search.
* @param needle The string to search for.
* @return The index of `needle` in `haystack`, or -1 if not found.
*/

//  algorithm kmp_search:
// input:
//     an array of characters, S (the text to be searched)
//     an array of characters, W (the word sought)
// output:
//     an array of integers, P (positions in S at which W is found)
//     an integer, nP (number of positions)

// define variables:
//     an integer, j ← 0 (the position of the current character in S)
//     an integer, k ← 0 (the position of the current character in W)
//     an array of integers, T (the table, computed elsewhere)

// let nP ← 0

// while j < length(S) do
//     if W[k] = S[j] then
//         let j ← j + 1
//         let k ← k + 1
//         if k = length(W) then
//             (occurrence found, if only first occurrence is needed, m may be returned here)
//             let P[nP] ← j - k, nP ← nP + 1
//             let k ← T[k] (T[length(W)] can't be -1)
//     else
//         let k ← T[k]
//         if k < 0 then
//             let j ← j + 1
//             let k ← k + 1
function indexOf(string haystack, string needle) public pure returns(int) {

bytes memory bhaystack = bytes(haystack);
bytes memory bneedle = bytes(needle);
uint needle_len = bneedle.length;
uint haystack_len = bhaystack.length;
// uint[] memory hashmem = new uint[](haystack_len);
if (needle_len > haystack_len) return -1;

// uint memory hayhashes = new uint[](haystack_len);

uint i;
uint needle_hash = 0;
uint haymult = 1;
uint hay_hash = 0;
uint back_hash = 0;

// if (i > 0)
//     hashmem[0] = 0;

for (i = 0; i < needle_len; i++) {
needle_hash *= 389;
needle_hash += uint8(bneedle[i]);
needle_hash %= 1000000007;
}

for (i = 0; i < needle_len; i++) {
hay_hash *= 389;
hay_hash += uint8(bhaystack[i]);
hay_hash %= 1000000007;
// hayhashes[i] = ;

haymult *= 389;
haymult %= 1000000007;
}
if ((back_hash * haymult + needle_hash) % 1000000007 == hay_hash) {
return int(i - needle_len);
}

for (; i < haystack_len; i++) {
hay_hash *= 389;
hay_hash += uint8(bhaystack[i]);
hay_hash %= 1000000007;

back_hash *= 389;
back_hash += uint8(bhaystack[i - needle_len]);
back_hash %= 1000000007;

if ((back_hash * haymult + needle_hash) % 1000000007 == hay_hash) {
return int(i - needle_len + 1);
}
}

return -1;
}
}

``````