C语言重构【28】实现 strStr()【KMP版】

你的名字 2022-12-08 12:52 171阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

实现 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() 定义相符。

#### 方案： ####

*  本题就是典型的KMP算法实现题

#include <iostream>
    #include <vector>
    
    using namespace ::std;
    
    //KMP 算法
    class Solution
    { 
    public:
        int strStr(string haystack, string needle)
        { 
            if (needle.empty())
                return 0;
            int i = 0, m = haystack.size();
            int j = 0, n = needle.size();
            vector<int> nextVal = get_nextVal(needle);
            while (i<m&&j<n)
            { 
                if(j==-1||needle[j]==haystack[i])i++,j++;
                else j = nextVal[j];
            }
            return j==n?i-j:-1;
        }
    
        vector<int> get_next(const string &pat)
        { 
            int n=pat.size();
            vector<int> next(n+1,-1);
            int k=-1,j=0;
            while(j<n){ 
                if(k==-1||pat[k]==pat[j]) next[++j]==++k;
                else k = next[k];
            }
            return next;
        }
    
        vector<int> get_nextVal(const string &pat)
        { 
            int n = pat.size();
            vector<int> nextVal(n, -1);
            int k = -1, j = 0;
            while (j < n - 1)
            { 
                if (k == -1 || pat[k] == pat[j])
                { 
                    k++, j++;
                    if (pat[j] != pat[k])
                        nextVal[j] = k;
                    else
                        nextVal[j] = nextVal[k];
                }
                else
                { 
                    k = nextVal[k];
                }
            }
            return nextVal;
        }
    };

[Git]: https://github.com/ch98road/leetcode