思路
kmp板子题
代码
class Solution {
public:
int strStr(string haystack, string needle) {
if(haystack == needle or needle == "") return 0;
// if(needle == )
int ne[(int)5e4 + 10];
haystack = "*" + haystack;
needle = "*" + needle;
// 构造next数组
for(int i = 2,j = 0;i<needle.size();i++)
{
while(j and needle[i] != needle[j+1]) j = ne[j];
if(needle[i] == needle[j+1]) j++;
ne[i] = j;
}
// kmp 字符串匹配
for(int i=1,j = 0;i<haystack.size();i++)
{
while(j and haystack[i] != needle[j+1]) j = ne[j];
if(haystack[i] == needle[j+1]) j++;
if(j == needle.size()-1)
{
return i - needle.size() + 1;
}
}
return -1;
}
};