力扣--28. 实现 strStr

• 【题目描述】
• 【示例】
• 【暴力搜索】
• • 【思路】
  • 【代码】

（简单题) )
今天的第二道简单题，先用了暴力搜索法，耗时比较长。

【题目描述】

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

原题传送门

【示例】

示例 1:

输入: haystack = “hello”, needle = “ll”
输出: 2

示例 2:

输入: haystack = “aaaaa”, needle = “bba”
输出: -1

说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

【暴力搜索】

【思路】

首先，特殊情况处理：needle为空字符串时，返回0，当needle的长度大于haystack时，返回-1；对于一般情况：直接遍历haystack，当haystack[i]==needle[0]，表明可能出现，先暂存当前的i.然后对比后面的每一位是否相符，相符则返回答案，不相符则将i置为之前记录的值+1继续找。
如果遍历完还没找到，就返回-1.

【代码】

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

执行结果：

暴力搜索耗时太长，再想想有没有更好的方法。
看了看解答区，发现这个问题叫做字符串匹配问题，常见的算法有：BF、BM、KMP三种，巧了，我居然一种都没听过。
对于前两种，好像应用没有那么广泛，所以先说说KMP算法吧。
看到两篇写的比较详细的解答：
KMP解法讲解1
KMP解法讲解2
以及B站的一个讲解视频：
KMP算法讲解视频
今天困了，下次再看。