The KMP (Knuth–Morris–Pratt) Algorithm with KMP Table.

kmp-algorithm-02.cs

public int StrStr(string haystack, string needle) {
    if (needle == null || needle == "") return 0;
    if (needle.Length > haystack.Length) return -1;
    if (needle.Length == haystack.Length) return haystack == needle ? 0 : -1;
    
    int[] lps = ComputeKMPTable(needle);
    
    int i = 0;
    int j = 0;
    
    while (i < haystack.Length) {
        if (haystack[i] == needle[j]) {
            i += 1;
            j += 1;
            if (j == needle.Length) return i - j; 
        } else {
            if (j != 0) 
            {
                j = lps[j - 1];
            }
            else 
            {
                i += 1; 
            }
        }
    }
    
    return -1;
}

private int[] ComputeKMPTable(string pattern) {
    int i = 1;
    int j = 0;
    int[] lps = new int[pattern.Length];
    while (i < pattern.Length) {
        if (pattern[i] == pattern[j]) {
            j += 1;
            lps[i++] = j;
        } else {
            if (j != 0) 
            {
                j = lps[j - 1];
            }
            else 
            {
                i += 1; 
            }
        }
    }
    return lps;
}