# **28-Implement strStr()**
###### tags: `Easy`、`String`

## Question
https://leetcode.com/problems/implement-strstr/

## Solution
### C++
* Use method: sliding window which window equals to needle, and use substring to compare with it.
* Or without using substr, also can initialize a string+=haystack[i]

class Solution {
public:
    int strStr(string haystack, string needle) {
        int l=haystack.size();
        int n=needle.size();
        for(int i=0; i<l;i++)
        {
            string s=haystack.substr(i,n);
            if(s==needle)
                return i;
        }
        return -1;
        
    }
};

### Python
- 想法:在haystack中，使用和needle相同長度尋找是否有字串符合needle

class Solution(object):
    def strStr(self, haystack, needle):
        if not needle:
            return 0
       
        for i in range(len(haystack) - len(needle) + 1):
            if haystack[i: i + len(needle)] == needle:
                return i
        return -1

## Solution
- 想法:直接使用python內建運算子in確認needle是否在haystack中，接著利用string函式.index找字串位置

class Solution(object):
    def strStr(self, haystack, needle):
        return haystack.index(needle) if needle in haystack else -1

## Solution
- KMP Algorithm

int strStr(string haystack, string needle){
        if(needle.size() == 0){
            return 0;
        }
        // KMP Algorithm to do the question in linear time.
        vector <int> v(needle.size(), -1);
        int j = 0, i = 1;
        while(i < v.size()){
            if(needle[i] == needle[j]){
                v[i] = j;
                i++;
                j++;
            }else if(j > 0){
                j = v[j - 1] + 1;
            }else{
                i++;
            }
        }
        
        i = 0, j = 0;
        while(i < haystack.size()){
            if(haystack[i] == needle[j]){
                if(j == needle.size() - 1){
                    return i - j;
                }
                i++;
                j++;
            }else if(j > 0){
                j = v[j - 1] + 1;
            }else{
                i++;
            }
        }
        
        
        return -1;
    }