LeetCode 28. 实现 strStr()-两种方法
原题链接
简单
作者:
bruce
,
2020-12-28 22:36:13
,
所有人可见
,
阅读 311
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
/**
* 28 实现strStr()函数
* 给定两个字符串,s和p,然后返回第一次匹配到p字符串的位置下标
* s = hello, b = ll
* return 2;
*/
/**
* 方法 1
* 设两个字符串的长度分别是 n 和 m, n表示s文本串的长度,m表示匹配串的长度
* 然后第一个指针从0开始到n-m+1遍历,因为只要遍历到剩下的字符长度大于第二个字符串长度位置
* 即可,然后第二个指针j从0开始到m,如果两个指针指向的字符不相同就直接退出,否则,第一个字符起始位置是从i+j开始,增量指针用法。
*/
int strStr1(string s, string p)
{
if (p.empty())
return 0;
int n = s.size(), m = p.size(); // 文本串和匹配串的长度
if (n < m) // 如果匹配串长度大于文本串,直接返回-1
return -1;
for (int i = 0; i < n - m + 1; ++i) // i <= n-m
{
int j = 0; // j从0开始,i+j开始遍历
for (j = 0; j < m; ++j)
{
if (s[i + j] != p[j]) // 如果当前不等,直接退出当前循环
break;
}
if (j == m)
return i;
}
return -1;
}
/**
* 方法 2,kmp算法,先生成一个next数组,然后使用kmp算法来做
*/
vector<int> getnext2(string s)
{
int j = -1;
vector<int> ne(s.size(), -1);
for (int i = 1; i < s.size(); i++)
{
while (j != -1 && s[i] != s[j + 1]) j = ne[j];
if (s[i] == s[j + 1]) j++;
ne[i] = j;
}
return ne;
}
int strStr(string s, string p)
{
if (p.empty()) return 0;
int m = p.size();
vector<int> ne = getnext2(p);
int j = -1, ans = 0;
for (int i = 0; i < s.size(); i++)
{
while (j != -1 && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j++;
if (j == m - 1) return i - m + 1;
}
return -1;
}