1public class Solution {
2    public int StrStr(string haystack, string needle) {
3        int m = haystack.Length;
4        int n = needle.Length;
5        if (n == 0) return 0;
6        for (int i = 0; i <= m - n; i++) {
7            int j = 0;
8            for (; j < n; j++) {
9                if (haystack[i + j] != needle[j])
10                    break;
11            }
12            if (j == n) return i;
13        }
14        return -1;
15    }
16    public static void Main() {
17        Solution sol = new Solution();
18        Console.WriteLine(sol.StrStr("sadbutsad", "sad")); // Output: 0
19    }
20}

1    public int StrStr(string haystack, string needle) {
        int m = haystack.Length;
        int n = needle.Length;
        if (n == 0) return 0;
        int[] lps = new int[n];
        computeLPSArray(needle, n, lps);
        int i = 0, j = 0;
        while (i < m) {
            if (haystack[i] == needle[j]) {
                i++;
                j++;
            }
            if (j == n) return i - j;
            else if (i < m && haystack[i] != needle[j]) {
                if (j != 0) j = lps[j - 1];
                else i++;
            }
        }
        return -1;
    }
    void computeLPSArray(string needle, int n, int[] lps) {
        int length = 0;
        lps[0] = 0;
        int i = 1;
        while (i < n) {
            if (needle[i] == needle[length]) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
    }
    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.StrStr("sadbutsad", "sad")); // Output: 0
    }
}