admin管理员组文章数量:1636900
Implement strStr()
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
算法思想:
循环扫描,比较直白
class Solution {
public:
char *strStr(char *haystack, char *needle) {
int size = strlen(haystack) - strlen(needle);
for (int i = 0; i <= size; i++) {
bool flag = true;
for (int j = 0; j < strlen(needle); j++) {
if (haystack[i + j] != needle[j]) {
flag = false;
break;
}
}
if (flag == true) {
return &haystack[i];
}
}
return NULL;
}
};
2、简单匹配算法BF算法
class Solution {
public:
char *strStr(char *haystack, char *needle) {
int slen = strlen(haystack);
int tlen = strlen(needle);
int i = 0 ,j = 0;
while ( i+j < slen && j < tlen){
if ( haystack[i+j] == needle[j] ){
j ++;
}
else
{
i ++;
j = 0;
}
}
if ( j >= tlen)
return &haystack[i];
else
return NULL;
}
};
3、KMP算法
KMP算法
class Solution {
public:
//代码4-1
//修正后的求next数组各值的函数代码
void get_nextval(char const* ptrn, int plen, int* nextval)
{
int i = 0;
nextval[i] = -1;
int j = -1;
while( i < plen-1 )
{
if( j == -1 || ptrn[i] == ptrn[j] ) //循环的if部分
{
++i;
++j;
if( ptrn[i] != ptrn[j] )
nextval[i] = j;
else
nextval[i] = nextval[j];
}
else
j = nextval[j];
}
}
char *strStr(char *haystack, char *needle) {
int slen = strlen(haystack);
int tlen = strlen(needle);
int i = 0 ,j = 0;
int *nextval=new int[tlen];
get_nextval(needle,tlen,nextval);
while ( i+j < slen && j < tlen){
if ( j == -1 || haystack[i+j] == needle[j] ){
j ++;
}
else
{
i ++;
j = nextval[j];
}
}
if ( j >= tlen)
return &haystack[i];
else
return NULL;
}
};
本文标签: OJLeetCodestrStrimplement
版权声明:本文标题:LeetCode OJ:Implement strStr() 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1729234775a1191866.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论