###### tags: `Leetcode` `easy` `string` `python` `c++`

# 28. Implement strStr()

## [題目來源:] https://leetcode.com/problems/implement-strstr/

## 題目:
Implement strStr().

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

## 解題想法:
求needle在haystack的起始位置
比較次數: 兩者長度相減 可以省去多餘的次數

## Python:

#28. Implement strStr()
class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        '''
        #這樣即可 但是最好不要直接調用函數
        new = haystack.find(needle,0,len(haystack))
        return new
        '''
        str1=len(haystack)
        str2=len(needle)
        if not str1 or not str2:
            return -1
        for pos in range(str1-str2+1):
            if haystack[pos:pos+str2]==needle:
                return pos
        return -1

if __name__ == '__main__':
    result = Solution()
    haystack = "hello" 
    needle = "ll"
    ans = result.strStr(haystack,needle)
    print(ans)

## C++

#include <iostream>
using namespace std;

class Solution
{
public:
    int strStr(string haystack, string needle)
    {
        int str1 = haystack.size();
        int str2 = needle.size();
        if (haystack.empty() || needle.empty())
            return -1;
        for (int i = 0; i < str1 - str2 + 1; i++)
        {
            // substr(起始位置,連續幾個)
            if (haystack.substr(i, str2) == needle)
                return i;
        }
        return -1;
    }
};

int main()
{
    string haystack = "hello", needle = "ll";
    Solution res;
    int pos = res.strStr(haystack, needle);
    cout << pos << endl;
    return pos;
}