接着讨论strstr()实现问题

ruoyisiyu

有一个贴子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[]) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;char *presult; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(3!=argc){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf("Usage:%s <dst> <src>\n",argv[0]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;exit(1); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;presult=my_strstr(argv[1],argv[2]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf("%s\n",presult); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;exit(0); } char *my_strstr(char *str,char *sub_str) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int i=0,j=0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while(str[i]!='\0'&&sub_str[j]!='\0') { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(str[i]==sub_str[j]) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;j++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i=i-j+1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;j=0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(sub_str[j]=='\0') &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return (char *)(str+i-j); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return NULL; }

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

gta

naive算法效率不高。用kmp

naihe2010

presult=my_strstr(argv[1],argv[2]);

这样申请空间，个别！

aero

原帖由 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

I386汇编的

;########################################################## ;strstr函数的实现。 ;使用_TEXT SEGMENT,_DATA SEGMENT伪指令 ;########################################################## PUBLIC    CRT_strstr _TEXT    SEGMENT CRT_strstr PROC  USES EBX ESI EDI lpStr:DWORD,lpSubStr:DWORD    &nbspROCSTART:         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    &nbspROCEXIT:         NOP         RET 8                    ;return to caller               CRT_strstr ENDP _TEXT    ENDS

EvilPhoenix

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 编辑 ]