问题链接

题目解析

实现函数strStr()。

解题思路

题意很简单，实现。这个函数是干什么的呢？简单来说，就是在一个字符串中寻找另一个字符串第一次出现的位置，未找到返回-1。

暴力解法

暴力匹配，直接遍历字符串，一个字符一个字符匹配下去，暴力代码如下：

class Solution {public:    int strStr(string haystack, string needle) {        if (needle.size() == 0) return 0;        if (needle.size() > haystack.size()) return -1;                int m = haystack.size(), n = needle.size();        for (int i = 0; i <= m - n; i++) {            int j = 0;            for (j = 0; j < n; j++) {                if (haystack[i + j] != needle[j]) break;            }            if (j == n) return i;        }        return -1;    }};

投机取巧法

由于在C++中，已经有实现此功能的函数——find。这里直接使用也可以过题，参考代码如下：

class Solution {public:    int strStr(string haystack, string needle) {        if (needle.size() == 0) return 0;        if (needle.size() > haystack.size()) return -1;        return haystack.find(needle);    }};

KMP匹配

还没有完全弄清楚，先码上~

---

本文版权归作者AlvinZH和博客园所有，欢迎转载和商用，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利.

---