首页 > 代码库 > 【leetcode】Implement strStr()
【leetcode】Implement strStr()
Implement strStr()
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
最简单的思路，逐一比较：
1 class Solution { 2 public: 3 int strStr(char *haystack, char *needle) { 4 5 int n1=strlen(haystack); 6 int n2=strlen(needle); 7 int result=-1; 8 bool flag; 9 for(int i=0;i<n1-n2+1;i++)10 {11 flag=true;12 for(int j=0;j<n2;j++)13 {14 if(haystack[i+j]==needle[j])15 {16 continue;17 }18 else19 {20 flag=false;21 break;22 }23 }24 25 if(flag==true)26 {27 result=i;28 break;29 }30 } 31 return result;32 }33 };
可以采用KMP算法：
KMP算法的核心是，当比较某两个字符不相等时，不必从头开始重新比较，而是根据引入的next，确定子串回溯的位置。
举个例子：
一个子串：
a | b | a | a | b | a | b | a |
-1 | 0 | 0 | 1 | 1 | 2 | 3 | 2 |
next[j]表示了如果在比较字符串时，needle[j]!=haystack[k]
那么下一次比较时，从next[j]所指定的位置进行比较，即j=next[j],k不变
1 class Solution { 2 public: 3 int strStr(char *haystack, char *needle) { 4 5 int i=0; 6 int j=0; 7 int n1=strlen(haystack); 8 int n2=strlen(needle); 9 10 vector<int> next=getNext(needle);11 12 while(i<n1&&j<n2)13 {14 if(j==-1||haystack[i]==needle[j])15 {16 i++;17 j++;18 }19 else20 {21 j=next[j];22 }23 }24 25 if(j==n2)26 {27 return i-j;28 }29 else30 {31 return -1;32 }33 }34 35 vector<int> getNext(char *needle)36 {37 int n=strlen(needle);38 39 vector<int> next(n);40 if(n==0)41 {42 return next;43 }44 45 next[0]=-1;46 47 int i=0;48 int k=-1;49 while(i<n-1)50 {51 if(k==-1||needle[k]==needle[i])52 {53 54 i++;55 k++;56 next[i]=k;57 }58 else59 { 60 k=next[k];61 }62 }63 64 return next;65 66 }67 68 };
对于k=next[k]
举个例子：如果比较最
a | b | a | a | b | a | b | a |
-1 | 0 | 0 | 1 | 1 | 2 | 3 | 2 |
最后一个元素的next为2
这是因为，倒数第二个元素与第四个元素不相等，此时
k=next[3]=1;
继续循环，
b==needle[k]=needle[1]
所以
i++
k++
得到
next[7]=2;
【leetcode】Implement strStr()
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。