子串搜索面试问题

Question

char* func( char* a, const char* b )
{
    while( *a )
    {
        char *s = a, *t = b;
        while( (*s++ == *t++) && *s && *t );

        if( *t == 0 )
            return a;
        a++;
    }
    return 0;       
}

编写上面的代码是为了在字符串"a"中搜索字符串"b"的第一个实例.

上述程序有问题吗？

有没有办法提高它的效率？

Answer 1

如果指向"cat"且b指向"ab",则func将返回指向"at"(错误值)而不是0(指定值)的指针,因为即使进行比较,指针t也会递增(*s ++ ==*t ++)失败.

为了完整起见,为了回答第二个问题,我提供了一个解决方案(当然还有其他可行的解决方案):将比较结果分配给另一个变量,例如while( ( flag = ( *s++ == *t++ ) ) && *s && *t );然后if( flag && *t == 0 ).

Answer 2

我不是C开发人员所以我不能也不会评论代码的正确性,但关于效率,请参阅:

http://en.wikipedia.org/wiki/String_searching_algorithm

我相信你有天真的搜索版本.看看Knuth-Morris-Pratt算法.b在搜索之前,您可以对字符串做一些工作a.然后你可以做到O(|a|+|b|).而|b|大于|a|则b不能在a如此就变成O(|a|).

其实质是,如果a是:

abcabe

并且b是:

aba

然后你知道如果第三个char失败,那么如果你移动b一个char或两个char,搜索也会失败.因此,您不必检查每个可能的子字符串:

a[1 .. 3] == b
a[2 .. 4] == b
...

这是O(|a|*|b|)字符,但只是一个等于的子集O(|a|)