题目:
题解:
class Solution {
public:
//解法1:库函数
int strStr_1(string haystack, string needle) {
return haystack.find(needle);
}
//解法2:暴力破解
int strStr_2(string haystack,string needle)
{
if(needle.empty())return -1;
int h=haystack.size(),n=needle.size();
//haystack的下标范围为[0,h-n]表示haystack的前h-n+1的字符都至少比较1次,当i取值为h-n时表示haystack中还有n的字符需与needle比较
for(int i=0;i<=h-n;++i)
{
int j=0;//每次循环重置j为0
for(;j<n;++j)
if(haystack[i+j]!=needle[j])
break;
if(j==n)return i;//找到匹配
}
return -1;//未找到匹配
}
//解法3:暴力破解显式回退
int strStr_3(string haystack,string needle)
{
int i=0,h=haystack.size();
int j=0,n=needle.size();
for(;i<h&&j<n;++i)
{
if(haystack[i]==needle[j])++j;
else {i-=j;j=0;}
}
//找到匹配,此时的i指向子串在文本串中尾元素之后的下标,需减去子串的长度得到第一个匹配成功的下标
if(j==n)return i-n;
//匹配不成功
else return -1;
}
};