# 3 Solutions and approximate to o(n+k)

• public class Solution {
private const int MINFASTLEN = 100;
private const int p = 100008;

public int StrStr(string haystack, string needle){
return StrStr_Faster(haystack, needle);
}

// first hash the needle and compare to sliding window on haystack.
// if match hash, check whether the string are exact match.
// Suppose the hash is good enough to have const number of conflicts, say c, the approximate time complexity should be O(c(n+k)) = O(n+k)
public int StrStr_Faster(string haystack, string needle){
if (String.IsNullOrEmpty(needle)) return 0;
if (haystack == null || needle == null) return -1;

int needleHash = 0;
var posWeight = 1;
for (int i = 0; i < needle.Length; i++){
needleHash = ((needleHash << 1) + (int)needle[i]) % p;
}
for (int i = 1; i < needle.Length; i++){
posWeight = (posWeight << 1) % p;
}

int slideHash = 0;
for (int i = 0; i < haystack.Length; i++)
{
if (i >= needle.Length){
slideHash = (((slideHash - posWeight * haystack[i - needle.Length]) % p) + p) % p;
}
slideHash = ((slideHash << 1) + haystack[i]) % p;
if (i + 1 >= needle.Length && slideHash == needleHash){
int j = 0;
while (j < needle.Length && haystack[i - needle.Length + 1 + j] == needle[j]) j++;
if (j == needle.Length) return i - needle.Length + 1;
}
}
return -1;
}

// use KMP to improve the long and sub-duplicated needle
public int StrStr_Fast(string haystack, string needle) {
if (String.IsNullOrEmpty(haystack) && String.IsNullOrEmpty(needle)) return 0;
if (haystack == null || needle == null) return -1;
var pointers = BuildFailPointers(needle);
var validStart = haystack.Length - needle.Length;
for (int i = 0, j = 0; i <= validStart; )
{
while (j < needle.Length && i + j < haystack.Length && haystack[i + j] == needle[j]) j++;
if (j == needle.Length) return i;
j = pointers[j] + 1;
i += j + 1;
}
return -1;
}

// basic implementation, O(n^2) force find
public int StrStr_Slow(string haystack, string needle) {
if (String.IsNullOrEmpty(haystack) && String.IsNullOrEmpty(needle)) return 0;
if (haystack == null || needle == null) return -1;
var validStart = haystack.Length - needle.Length;
for (int i = 0; i <= validStart; i++){
int j = 0;
while (j < needle.Length && haystack[i + j] == needle[j]) j++;
if (j == needle.Length) return i;
}
return -1;
}

private int[] BuildFailPointers(string str){
if (String.IsNullOrEmpty(str)) return new int[0];
var pointers = new int[str.Length];
pointers[0] = -1;
for (int i = 1; i < str.Length; i++){
int j = pointers[i - 1];
while (j >= 0 && str[j + 1] != str[i]){
j = pointers[j];
}
if (j < 0) pointers[i] = -1;
else pointers[i] = j + 1;
}
return pointers;
}

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.