一個有難度的題目

soul_of_moon

正确的如下：
#include <stdio.h>

int substring(const char *src,char *des);
int isSubString(char *src,char *des);

int main()
{
    char aSrc[]="abcdesdfdfg";
    char aDes[]="\0";
    printf("%d\n",substring(aSrc,aDes));
    return 0;
}

int substring(const char *src,char *des)
{
        if(NULL==src || NULL==des||'\0'==*des)
        {
                return 0;
        }
    int iCount=0;
    char *pcTmp=(char *)src;
    while('\0'!=*pcTmp)
    {
        if(0==isSubString(pcTmp,des))
        {
                iCount++;
        }
        pcTmp++;
    }
    return iCount;
}

int isSubString(char *src,char *des)
{
        if(NULL==src || NULL==des ||'\0'==*des)
        {
                return -1;
        }
    while('\0'!=*des)
    {
        if(*src!=*des)
        {
                return -1;
        }
        src++;
        des++;
    }
    return 0;
}
想了想还是把这个判断放上，可以增加效率

[ 本帖最后由 soul_of_moon 于 2006-4-7 16:09 编辑 ]

g9527j

我想看看kmp算法，哪位大俠知道。謝謝。
   
soul_of_moon  
正確

kimyoung

char aSrc[]="abbbddfkjkl;j;kjlkj;";
    char aDes[]="bb\0";

    楼上的程序有问题，上面这种情况没有考虑！

g9527j

大家看看有没有更好的算法，

hkwang66

原帖由 g9527j 于 2006-4-7 17:22 发表
我想看看kmp算法，哪位大俠知道。謝謝。
   
soul_of_moon  
正確

老严的数据结构的书上就有（第二版上 第四章 串）

bitbull

原帖由 g9527j 于 2006-4-7 23:19 发表
大家看看有没有更好的算法，

我的解答呢?

redbison

任何一本数据结构的书都要讲这个问题，顺序比较或者KMP。楼主这么偷懒来这里套答案，太偷懒了，估计是要(刚)毕业的没有认真学习的学生。太过头了。

xjx79

其实，如果判断子串个数的话，那么，对于，有重复出现的情况，
如：
母串："bbbbccbbccbbcbbbb"
子串："bb"
结果应为多少呢？
有两种可能，一种：8，一种：6
又如：
母串："abcabcabcaddd"
子串："abca"
也有两种可能，一种：3，一种：2

到底是那种，要看你目的是做什么的了，
其实，soul_of_moon兄的代码正确的，正是第一种类型，对于重复字符可以在计算，
如果要实现第二种答案：
需要将
int substring(const char *src,char *des)
{
        int iCount=0;
        char *pcTmp=(char *)src;
        while('\0'!=*pcTmp)
        {
                if(0==isSubString(pcTmp,des))
                {
                        iCount++;
                }
                pcTmp++;
        }
        return iCount;
}
改为
int substring(const char *src,char *des)
{
        int iCount=0;
        char *pcTmp=(char *)src;
        while('\0'!=*pcTmp)
        {
                if(0==isSubString(pcTmp,des))
                {
                        iCount++;
                        pcTmp+=strlen(des);
                }
                else
                        pcTmp++;
        }
        return iCount;
}

xjx79

bitbull ，你好，
你的代码也有问题，

在while(*desp && *srcp++ == *desp++) 这段代码上有问题，
因为后置++事先使用在偏移，所以不对，因改为前置++，
即改为while(*desp && *++srcp == *++desp)

对于在"bbbcbbb"中查找"bb"，后置++，为4是错误值，前置++，为2，是正确的

主要原因为：在你循环执行完后，desp可能仍然指向'\0'，所以result仍然加一，导致结果不正确

第一次循环，srcp->bbbcbbb,desp->bb, 相等
循环结束时，srcp->bbcbbb,desp->b,
第二次循环，srcp->bbcbbb,desp->b, 相等
循环结束时，srcp->bcbbb,desp->\0,
第三次循环，srcp->bcbbb,desp->bb, 相等
循环结束时，srcp->cbbb,desp->b,
第四次循环，srcp->cbbb,desp->b, 不相等，
退出循环，srcp->bbb,desp->\0,

所以导致，误认为相等，使result+1;

bitbull

原帖由 xjx79 于 2006-4-9 17:04 发表
bitbull ，你好，
你的代码也有问题，

在while(*desp && *srcp++ == *desp++) 这段代码上有问题，
因为后置++事先使用在偏移，所以不对，因改为前置++，
即改为while(*desp && *++srcp ==  ...

不好意思,代码在从虚拟机抄过来的时候打错了.
我以为我在测试你的bbbcbb的时候结果怎么是正确的.

原代码是前缀++没错.谢谢指出.