首页 > 代码库 > Implement strStr()
Implement strStr()
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
思路：这是一道字符串匹配的函数，就是找出needle在haystack首次出现的位置。暴力解决，简单明了。
class Solution {public: char *strStr(char *haystack, char *needle) { int hay_len=strlen(haystack); int nee_len=strlen(needle); for(int i=0;i<=hay_len-nee_len;i++) { char *str=haystack+i; char *sub_str=needle; while(*sub_str!=‘\0‘) { if(*str==*sub_str) { str++; sub_str++; } else break; } if(*sub_str==‘\0‘) return haystack+i; } return NULL; }};
思路二：使用KMP算法。关键就是next函数如何得到。大家可以借鉴一下KMP算法之总结篇（12.09修订，必懂KMP和KMP字符串模式匹配详解，讲得很详细。
class Solution {public: void get_nextval(char *needle,int nextval[]) { int i=0; nextval[0]=-1; int j=-1; while(i<strlen(needle)) { if(j==-1||needle[i]==needle[j]) { i++; j++; nextval[i]=j; } else j=nextval[j]; } } char *strStr(char *haystack, char *needle) { int hay_len=strlen(haystack); int nee_len=strlen(needle); int i=0,j=0; int *nextval=new int[nee_len+1]; get_nextval(needle,nextval); while(i<hay_len&&j<nee_len) { if(j==-1||haystack[i]==needle[j]) { i++; j++; } else j=nextval[j]; } if(j==nee_len) return &haystack[i-nee_len]; return NULL; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。