【LeetCode 21】28. 实现 strStr()
文章目录
一、题意
二、思考过程
2.1构造next数组
构造next数组就是计算模式串s的前缀表的过程,分三步:
- 初始化next数组:
int j=0;//前缀末尾
next[0]=0;//后缀末尾
for(int i=1;i<s.size();i++){
xxx;//各种操作
}
- 处理前后缀不相同的情况:
a≠b,前后缀不相同,j回退前一位进行跳转。
for(int i=1;i<s.size();i++){
//前后缀不同时
while(s[i]!=s[j])
{
j=next[j-1];
}
}
- 处理前后缀相同的情况:
a=a,前后缀相同,匹配成功,那么直接j往后移动
for(int i=1;i<s.size();i++){
//前后缀不同时
while(s[i]!=s[j])
{
j=next[j-1];
}
//前后缀相同
if(s[i]==s[j])
{
j++;
}
}
三、完整代码
class Solution {
public:
//haystack:文本串
//needle:模式串
int strStr(string haystack, string needle)
{
if(needle.size()==0) return 0;//模式串为空
int next[needle.size()];//初始化next数组长度
getNext(next,needle);//构建next数组
int j=0;
for(int i=0;i<haystack.size();i++)
{//遍历文本串
while(j>0&&haystack[i]!=needle[j])
{
j=next[j-1];//出现不匹配时j开始回退跳转
}
if(haystack[i]==needle[j])
{
j++;//出现匹配时j指针往前移动
}
if(j==needle.size())//文本串中出现了模式串的子串
{
return (i-needle.size()+1);//匹配成功返回下标索引
}
}
return -1;//返回失败
}
//构建next数组
void getNext(int *next,const string &s)
{
int j=0;
next[0]=0;
for(int i=1;i<s.size();i++)
{
while(j>0&&s[i]!=s[j])
{
j=next[j-1];
}
if(s[i]==s[j])
{
j++;
}
next[i]=j;
}
}
};