LeetCode -- Implement strStr()

LeetCode -- Implement strStr()

題目描述：
Implement strStr().


Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.


其實就是要實現一個查找子字符串起始位置的函數。




思路：
本文采用的是傳統解法，兩層遍歷，對於字符串haystack的逐個字符往後移動，判斷haystack[i...needle.Length]是否等於needle即可。


更快的算法是KMP，這兩篇文章講的非常清楚：
http://blog.csdn.net/v_july_v/article/details/7041827
http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html




實現代碼：

public class Solution {
    public int StrStr(string haystack, string needle) {
        var i = 0;
        while(i < haystack.Length - needle.Length + 1){
            var k = i;
            while(k < haystack.Length - needle.Length + 1){
				var s = haystack.Substring(k, needle.Length);
                if(s == needle){
                    return k;
                }
				k++;
            }
			i++;
        }
        return -1;
    }
}