不使用已有的系统调用或函数库,实现c库的函数:strstr()

mik

原帖由 "mq110" 发表：
还有 你的程序不符合 strstr的函数原形
char *strstr(const char *haystack, const char *needle);

既然能用while 改. 我想你也不必再用goto.

当时感觉用while(1)循环, 可能会每次循环做一次判断.
     而且,用goto感觉好点,简洁些.是根据算法而想的.
如果原型改为 char *(const char* s, const char *d); 就更容易实现了.

char * __strstr(const char *s, const char *d)
{
         int ret = 0;
         int i = 0, j = 0;

loop:

         if (*(d+i) == *(s+j)) {
                   i++;  j++;
                   if (*(d+i) == '\0')
                            return s + ret;
                   goto loop;

         } else {
                  i = 0;
                  ret++;   j = ret;
                  if (*(s+j) == '\0')
                         return 0;
                  goto loop;
         }
}

slwrq

char * strstr(const char * s1,const char * s2)
{
       int l1, l2;

       l2 = strlen(s2);
       if (!l2)
               return (char *) s1;
       l1 = strlen(s1);
       while (l1 >= l2) {
               l1--;
               if (!memcmp(s1,s2,l2))
                       return (char *) s1;
               s1++;
       }
       return NULL;
}

xiaofeng_jia

抽空写了一个

/* filename my_strstr.c */

#include <unistd.h>
#include <stdio.h>
#include <assert.h>


char *my_strstr(const char *string, const char *string_set)
{
        assert(NULL != string);
        assert(NULL != string_set);
       
        char *str_src= (char *)string;
        char *str_set = (char *)string_set;
        char *str_rut = NULL;
       
        while ( '\0' != *str_src ) {
                str_rut = str_src;
                for ( ; *str_src++ == *str_set; ) {
                        str_set++;
                        if ( '\0' == *str_set ) {
                                return str_rut;
                        }
                }
        }
       
        return NULL;
}

int main(void)
{
        char *str_tmp = NULL;
        char string_1[]="453gh3u";
        char *string_2="What's your name";

        str_tmp = my_strstr(string_1, "abc");
        printf("[%s]\n%s\n",string_1, str_tmp);

        str_tmp = my_strstr(string_2, "your");
        printf("[%s]\n%s\n", string_2, str_tmp);
       
        return 0;
}

oyjcq

http://www.cublog.cn/u/1807/?u=h ... howart.php?id=89570
这个合适吧， 返回的地方改下就好了

emacsnw

简单看了一把，全是naive的O(m*n)算法。KMP不是可以O(m+n)吗？

luojiannx

想想,确实可以做到更有效率点
比较第一个字符相同后,直接比较搜索字符串的最后一个字符（指针都+strlen（dest))
如果最后一个字符相同还是逐个比较
如果不同再从刚才加的长度+1处开始比较
O(m+n)是这样的么？这个如果理想情况下，效率比m+n还好呢，（m/n)+n

如果像62楼所说的
那么linux内核“也不是处处考虑周到（起码在效率方面,这个应该不要考虑可读性吧）