学步园

函数strstr的原型是char *strstr(char *str1, char *str2); 其功能是在str1中返回指定字符串str2的第一次出现的位置。 

#include <stdio.h><br /> #include <string.h><br /> int main(void)<br /> {<br /> char *str1 = "Borland International", *str2 = "nation", *ptr;<br /> ptr = strstr(str1, str2);<br /> printf("The substring is: %s/n", ptr);<br /> return 0;<br /> }<br /> /*<br /> output:<br /> The substring is: national<br /> */

下面是实现strstr功能的一种方法。(注：有错误！
)

/*<br /> Modification date: 2010-5-28<br /> test:<br /> src: abcd efghcd abcdef<br /> dst: cd<br /> return: cd efghcd abcdef<br /> */<br /> #include <cstdio><br /> #include <cstring>// strlen, strstr<br /> #include <cassert>// assert<br /> char* my_strstr(char* src,char* dst)<br /> {<br /> // check<br /> assert(src);<br /> assert(dst);</p> <p> // calculate the each size<br /> char *szSrc = src,*szDst = dst;<br /> int nSrcSize = strlen(szSrc), nDstSize = strlen(szDst);<br /> // check<br /> if (nSrcSize < nDstSize)<br /> {<br /> return NULL;// error<br /> }<br /> // compare<br /> int nCompareCount = nSrcSize-nDstSize+1;<br /> int i,j;<br /> for (i = j = 0; i<nSrcSize && j<nDstSize; ++i)<br /> {<br /> if (src[i] != dst[j])<br /> {<br /> if (i == nCompareCount-1)// this check can save time<br /> {<br /> return NULL;// no substring<br /> }<br /> j = 0;<br /> }<br /> else// to find the first same value<br /> {<br /> ++j;<br /> }<br /> }<br /> if (j == nDstSize)// absolute equal<br /> {<br /> return &src[i-nDstSize];// have substring<br /> }<br /> return NULL;// no substring<br /> }<br /> int main()<br /> {<br /> //char *szSrc = "wcdj is a guy", *szDst = "is";<br /> char szSrc[128] = {0}, szDst[128] = {0};<br /> printf("input src: ");<br /> //scanf("%s",szSrc);<br /> gets(szSrc);<br /> printf("input dst: ");<br /> //scanf("%s",szDst);<br /> gets(szDst);<br /> // call my function<br /> char* ptr = my_strstr(szSrc,szDst);<br /> if (ptr)<br /> {<br /> printf("The substring is: %s/n", ptr);<br /> }<br /> else<br /> {<br /> printf("has no substring/n");<br /> }<br /> getchar();<br /> return 0;<br /> }

上述方法只考虑了目的字符串dst的回溯，但是没有考虑源字符串src的回溯，纠正如下：使用nNext记录回溯的位置。

/*<br /> Modification date: 2011-4-13<br /> test:<br /> src: xxy<br /> dst: xy<br /> return: xy<br /> */<br /> #include <cstdio><br /> #include <cstring>// strlen, strstr<br /> #include <cassert>// assert<br /> char* my_strstr(char* src, char* dst)<br /> {<br /> // check<br /> assert(src);<br /> assert(dst);</p> <p> // calculate the each size<br /> char *szSrc = src,*szDst = dst;<br /> int nSrcSize = strlen(szSrc), nDstSize = strlen(szDst);<br /> // check<br /> if (nSrcSize < nDstSize)<br /> {<br /> return NULL;// error<br /> }<br /> // compare<br /> int nCompareCount = nSrcSize-nDstSize+1;<br /> int nNext = 0;<br /> bool bFirst = false;<br /> int i = 0, j = 0;<br /> while (i < nSrcSize && j < nDstSize)<br /> {<br /> if (src[i] != dst[j])<br /> {<br /> if (--nCompareCount == 0)// save time<br /> {<br /> return NULL;// no substring<br /> }<br /> // backtrace<br /> j = 0;<br /> if (bFirst)<br /> {<br /> i = nNext;<br /> bFirst = false;<br /> continue;<br /> }<br /> }<br /> else<br /> {<br /> ++j;<br /> if (bFirst == false)<br /> {<br /> nNext = i+1;<br /> bFirst = true;<br /> }<br /> }<br /> ++i;<br /> }<br /> if (j == nDstSize)// absolute equal<br /> {<br /> return &src[i-nDstSize];// have substring<br /> }<br /> return NULL;// no substring<br /> }<br /> int main()<br /> {<br /> char szSrc[128] = {0}, szDst[128] = {0};<br /> printf("input src: ");<br /> fgets(szSrc, sizeof(szSrc), stdin);<br /> printf("input dst: ");<br /> fgets(szDst, sizeof(szDst), stdin);<br /> // clear '/n' in the end of string<br /> szSrc[strlen(szSrc)-1] = '/0';<br /> szDst[strlen(szDst)-1] = '/0';<br /> char* ptr = my_strstr(szSrc,szDst);<br /> if (ptr)<br /> {<br /> printf("The substring is: %s/n", ptr);<br /> }<br /> else<br /> {<br /> printf("has no substring/n");<br /> }<br /> getchar();<br /> return 0;<br /> }