Chinaunix

标题: 接着讨论strstr()实现问题 [打印本页]

作者: ruoyisiyu 时间: 2007-09-01 12:09
标题: 接着讨论strstr()实现问题
有一个贴子http://bbs.chinaunix.net/thread-588892-1-1.html
题目是“不使用以有的系统调用或函数库实现strstr()”,有人贴了如下代码

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

char *my_strstr(char *,char *);
int
main(int argc,char *argv[])
{

        char *presult;
        if(3!=argc){
                printf("Usage:%s <dst> <src>\n",argv[0]);
                exit(1);
        }
        presult=my_strstr(argv[1],argv[2]);
        printf("%s\n",presult);
        exit(0);
}

char *my_strstr(char *str,char *sub_str)
{
       int i=0,j=0;
        while(str[i]!='\0'&&sub_str[j]!='\0') {
                if(str[i]==sub_str[j]) {
                        i++;
                        j++;
                }
                else {
                        i=i-j+1;
                        j=0;
                }
        }
        if(sub_str[j]=='\0')
                return (char *)(str+i-j);
        return NULL;
}

我想不用指针的下标形式如何实现？？

作者: gta 时间: 2007-09-01 15:15
naive算法效率不高。用kmp

作者: naihe2010 时间: 2007-09-04 15:40
presult=my_strstr(argv[1],argv[2]);

这样申请空间，个别！

作者: aero 时间: 2007-09-04 16:07

原帖由 gta 于 2007-9-1 15:15 发表
naive算法效率不高。用kmp

除非sub str很长或者有很多重复字符，否则KMP算法没有比这种循环快多少。KMP的最大优势在于不用回溯。

原帖由 naihe2010 于 2007-9-4 15:40 发表
presult=my_strstr(argv[1],argv[2]);

这样申请空间，个别！

不是申请空间吧？

作者: ChinaDream 时间: 2007-09-04 17:12
I386汇编的

;##########################################################
;strstr函数的实现。
;使用_TEXT SEGMENT,_DATA SEGMENT伪指令
;##########################################################
PUBLIC    CRT_strstr

_TEXT    SEGMENT

CRT_strstr PROC USES EBX ESI EDI lpStr:DWORD,lpSubStr:DWORD

   &nbsp

ROCSTART:
        MOV ESI,[EBP+8]       ;ESI=lpStr
        MOV EBX,[EBP+12]        ;EBX=lpSubStr
        MOV EDI,EBX                ;EDI=lpSubStr
    FIRSTCMP:
        XOR ECX,ECX          ;ECX=0
        XOR EDX,EDX          ;EDX=0
        MOV CL,[ESI]          ;CL=(*lpStr)
        MOV DL,[EDI]          ;DL=(*lpSubStr)
        CMP CL,0h             ;
        JZ  ZERORETURN       ;if((*ESI)==0) GOTO ZERORETURN
        CMP DL,0h             ;
        JZ  ZERORETURN       ;if((*EDI)==0) GOTO ZERORETURN
        NOP
        CMP CL,DL             ;
        JE  READYSECCMP       ;if((*ESI)==(*EDI)) GOTO READYSECCMP
        INC ESI                ;ESI++
        JMP FIRSTCMP          ;if((*ESI)!=(*EDI)) GOTO FIRSTCMP
    READYSECCMP:
        MOV EAX,ESI          ;EAX=ESI (recording ret addr)
    SECONDCMP:
        INC ESI                ;ESI++
        INC EDI                ;EDI++
        XOR ECX,ECX          ;ECX=0
        XOR EDX,EDX          ;EDX=0
        MOV CL,[ESI]          ;CL=(*ESI)
        MOV DL,[EDI]          ;DL=(*EDI)
        NOP
        CMP DL,0h             ;
        JZ  PROCEXIT           ;if((*EDI)==0) GOTO PROCEXIT (Successful Matched)
        CMP CL,0h             ;
        JZ  ZERORETURN       ;if((*ESI)==0) GOTO ZERORETURN
        NOP
        CMP CL,DL             ;
        JE  SECONDCMP          ;if(CL=DL) GOTO SECONDCMP
        MOV EDI,EBX               ;ECX=lpSubStr
        JNE FIRSTCMP          ;else GOTO FIRSTCMP
    ZERORETURN:
        XOR EAX,EAX          ;EAX=NULL
   &nbsp

ROCEXIT:
        NOP
        RET 8                    ;return to caller     
CRT_strstr ENDP

_TEXT    ENDS

作者: EvilPhoenix 时间: 2007-09-30 08:48
const char* my_strstr(char* str,char* substr)
{
   assert(str && substr);
   const char* p=s1, *r=s2;
   while(*p!='\0')
   {
      while(*p++==*r++);
      if(*r=='\0')
            return p;
      else
      {
            r=s2;
            p=++s1;
      }
   }
   return NULL;
}

[ 本帖最后由 EvilPhoenix 于 2007-10-7 20:29 编辑 ]

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)