The KMP (Knuth–Morris–Pratt) Algorithm.

kmp-algorithm.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 j = 0;
    int nextMatchingHeadIndex = 0;
    bool isMatchingHeadFound = false;
    for (int i = 0; i < haystack.Length; i++)
    {
        if (j == 0 && haystack.Length - i < needle.Length) return -1;

        if (!isMatchingHeadFound)
        {
            if (j > 0 && haystack[i] == needle[0])
            {
                nextMatchingHeadIndex = i - 1;
                isMatchingHeadFound = true;
            }
            else
            {
                nextMatchingHeadIndex = i;
            }
        }

        if (haystack[i] == needle[j])
        {
            j += 1;
            if (j == needle.Length) return i - j + 1;
        }
        else
        {
            i = nextMatchingHeadIndex;
            j = 0;
            isMatchingHeadFound = false;
        }
    }

    return -1;
}