solution.md

# 实现 strStr()

<p>实现 <a href="https://baike.baidu.com/item/strstr/811469" target="_blank">strStr()</a> 函数。</p>
<p>给你两个字符串 <code>haystack</code> 和 <code>needle</code> ，请你在 <code>haystack</code> 字符串中找出 <code>needle</code>
    字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  <code>-1</code><strong> </strong>。</p>

<p><strong>说明：</strong></p>
<p>当 <code>needle</code> 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。</p>
<p>对于本题而言，当 <code>needle</code> 是空字符串时我们应当返回 0 。这与 C 语言的 <a href="https://baike.baidu.com/item/strstr/811469"
        target="_blank">strstr()</a> 以及 Java 的 <a
        href="https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#indexOf(java.lang.String)"
        target="_blank">indexOf()</a> 定义相符。</p>

<p><strong>示例 1：</strong></p>
<pre><strong>输入：</strong>haystack = "hello", needle = "ll"<strong><br />输出：</strong>2</pre>
<p><strong>示例 2：</strong></p>
<pre><strong>输入：</strong>haystack = "aaaaa", needle = "bba"<strong><br />输出：</strong>-1</pre>
<p><strong>示例 3：</strong></p>
<pre><strong>输入：</strong>haystack = "", needle = ""<strong><br />输出：</strong>0</pre>

<p><strong>提示：</strong></p>
<ul>
    <li><code>0 <= haystack.length, needle.length <= 5 * 10<sup>4</sup></code></li>
    <li><code>haystack</code> 和 <code>needle</code> 仅由小写英文字符组成</li>
</ul>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```c
#include <bits/stdc++.h>
using namespace std;
```

### after

```c
int main()
{
    Solution sol;
    int res;
    res = sol.strStr("hello", "ll");
    cout << res;
    return 0;
}
```

## 答案

```c
class Solution
{
public:
    int strStr(string haystack, string needle)
    {
        return haystack.find(needle);
    }
};
```
## 选项


### A

```c
class Solution
{
public:
    int strStr(string haystack, string needle)
    {
        int l1 = haystack.size();
        int l2 = needle.size();
        int i = 0, j = 0;
        while (i < l1 && j < l2)
        {
            if (haystack[i] == needle[j])
            {
                i++;
                j++;
            }
            else
            {
                i = i - j + 1;
                j = 0;
            }
        }
        if (j >= l2)
            return (i - j);
        else
            return -1;
    }
};
```

### B

```c
class Solution
{
public:
    vector<int> next(string str)
    {
        vector<int> v;
        v.push_back(-1);
        int i = 0, j = -1;
        while (i < str.size())
        {
            if (j == -1 || str[i] == str[j])
            {
                ++i;
                ++j;
                v.push_back(j);
            }
            else
                j = v[j];
        }
        return v;
    }
    int strStr(string haystack, string needle)
    {
        int i = 0;
        int j = 0;
        int len1 = haystack.size(), len2 = needle.size();
        vector<int> nextptr;
        if (needle.empty())
            return 0;

        nextptr = next(needle);

        while ((i < len1) && (j < len2))
        {

            if ((j == -1) || (haystack[i] == needle[j]))

            {
                i++;
                j++;
            }
            else
            {
                j = nextptr[j];
            }
        }

        if (j == needle.size())
            return i - j;
        else
            return -1;
    }
};
```

### C

```c
class Solution
{
public:
    int strStr(string haystack, string needle)
    {
        int flag = 0;
        int i, j;
        int sizeofh = haystack.length();
        int sizeofn = needle.length();
        if (needle == "")
        {
            return 0;
        }
        for (i = 0; i < sizeofh; i++)
        {
            for (j = 0; j < sizeofn; j++)
            {
                if (i + j > sizeofh)
                {
                    break;
                }
                if (haystack[i + j] != needle[j])
                {
                    break;
                }
            }
        }
        if (flag)
        {
            return i;
        }
        else
            return -1;
    }
};
```