一、题意
二、思考过程
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; } } };
