# \#28 Implement strStr() 查找字串
## *給定兩個string:haystack和needle, 回傳needle出現在haystack的位置index*
## Log
- build 20210402 by syhuang

## KMP(字串查找演算法)
- 建立字串查找表, 根據此表跑單層迴圈找字串出現位置, 時間複雜度降低至O(n)

var strStr = function(haystack, needle) {
    var m = haystack.length, n = needle.length;
    if(!n) return 0;
    var lps = kmpProcess(needle);
    for(var i = 0, j = 0; i < m;) {
        if(haystack[i] == needle[j]) {
            i++, j++;
        }
        if(j == n) return i - j;
        if(i < m && haystack[i] != needle[j]) {
            if(j) j = lps[j - 1];
            else i++;
        }
    }
    return -1;
};

var kmpProcess = function(needle) {
    var n = needle.length;
    var lps = new Array(n).fill(0);
    for (var i = 1, length = 0; i < n;) {
        if(needle[i] === needle[length]) {
            length++;
            lps[i] = length;
            i++;
        } else if (length) length = lps[length - 1];
        else {
            lps[i] = 0; 
            i++;
        }
    }
    return lps;
}

## 語言專屬解法(其實很多語言都有查找字串方法了)
- javascript已有String.indexOf()方法可用

var strStr = function(haystack, needle) {
    return haystack.indexOf(needle);
};

## 初見
- 暴力破解:跑兩層for loop, 外層是haystack, 內層needle, 逐個比對字元, 時間複雜度是O(n^2)
<br>當字元不相等 - 內層break
<br>當內層比對到j==needle.length-1表示haystack存在needle這個字串,回傳i即可

var strStr = function(haystack, needle) {
    if(needle=='') return 0;
    if(haystack=='') return -1;
    if(haystack.length < needle.length) return -1;
    var find = false;
    for(var i=0; i<=haystack.length - needle.length ; i++){
        for(j=0; j<needle.length; j++){
            if(haystack.charAt(i+j)!=needle.charAt(j)) break;
            if(j==needle.length-1) return i;
        }
    }
    return -1;
};

## 備註
## 參考
[KMP實作by javascript來源](https://leetcode.com/problems/implement-strstr/discuss/13034/JavaScript-KMP-beats-95)
###### tags: `leetcode`, `leetcode-easy`