28. 找出字符串中第一个匹配项的下标
给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。文章来源地址https://www.toymoban.com/news/detail-689091.html
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.size()==0){
return 0;
}
int length1=haystack.size();
int length2=needle.size();
vector<int> next(needle.size());
//初始化
next[0]=0;
int j=0;//前缀的末尾位置,同时也是前后缀相同元素的个数
int i=1;//后缀的末尾位置
for(int i=1;i<needle.size();i++){
while(needle[j]!=needle[i] && j>0){
j=next[j-1];
}
if(needle[j]==needle[i]){
j++;
}
next[i]=j;
}
j=0;
for(int i=0;i<haystack.size();i++){
while(j>0 && haystack[i]!=needle[j]){
j=next[j-1];
}
if(haystack[i]==needle[j]){
j++;
}
if(j==needle.size()){
return (i-needle.size()+1);
}
}
return -1;
}
};
文章来源:https://www.toymoban.com/news/detail-689091.html
到了这里,关于28. 找出字符串中第一个匹配项的下标的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!