子串搜索面试问题
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”的第一个实例。
上述程序有问题吗？
有没有办法提高它的效率？
如果指向“cat”且b指向“ab”，则func将返回指向“at”（错误值）而不是0（指定值）的指针，因为即使比较（* s ++）指针t也会递增== * t ++）失败。
为了完整起见，为了回答第二个问题，我提供了一个解决方案（当然还有其他可行的解决方案）：将比较结果分配给另一个变量，例如while( ( flag = ( *s++ == *t++ ) ) && *s && *t ); 然后if( flag && *t == 0 ) 。
我不是C开发人员所以我不能也不会评论代码的正确性，但关于效率，请参阅：
http://en.wikipedia.org/wiki/String_searching_algorithm
我相信你有天真的搜索版本。 看看Knuth-Morris-Pratt算法。 在搜索之前，你可以对字符串b做一些工作。 然后你可以在O(|a|+|b|) 。 并|b| 大于|a| 然后b不能在a所以它变成O(|a|) 。
实质是如果a是：
abcabe
而b是：
aba
然后你知道如果第三个char失败，那么如果你移动一个char或两个char，搜索也会失败。 因此，您不必检查每个可能的子字符串：
a[1 .. 3] == b a[2 .. 4] == b ...
哪个是O(|a|*|b|)字符，但只有一个等于O(|a|)的子集O(|a|)
是啊…
- t不能被指定为b作为其破坏const。
- 它与“b”中的最后一个字符不匹配。
嗯，确实有一个小问题，它实际上没有用。
尝试使用=“xyz”和b =“xw”运行。 当你第一次点击while循环时，x = x，你增加两个指针，然后再循环。 然后y！= w，所以你退出循环。 但是你已经增加了指针，所以t == 0，你报告一个命中。
通常，无论最后一个字符是否匹配，都会报告匹配。
如果b是1个字符的字符串，则最后一个字符是唯一的字符，因此1个字符的字符串匹配任何内容。
我建议不要尝试使用带有副作用的单个语句来执行循环。 如这个例子所示，这很棘手。 即使你做对了，对于试图阅读你的代码的人来说也是非常神秘的。
你可以将’while循环’重写为（不使用标志）：
while( (*s == *t) && *s && *t ){ s++; t++; }
或者使用for循环…下面的代码是从’C’的K＆R书中复制的：
/* strindex: return index of t in s, -1 if none */ int strindex(char s[], char t[]) { int i, j, k; for (i = 0; s[i] != '\0'; i++) { for (j=i, k=0; t[k]!='\0' && s[j]==t[k]; j++, k++) ; if (k > 0 && t[k] == '\0') return i; } return -1; }
- 如果
a没有正确地以null结尾，那么该函数将会死得很厉害。 - 如果
b没有正确地以null结尾，那么该函数可能会死得很厉害。 - 缩进很奇怪。
这将完成这项工作，但我有更好的方法来做到这一点。 查看这篇文章： http ： //en.wikipedia.org/wiki/String_searching_algorithm
我认为这一行：
while( (*s++ == *t++) && *s && *t );
未定义，因为您在增量之前或增量之后可能在后增量之后访问变量。
除非他们改变它，否则标准的副作用在它们生效的时候是不明确的。 唯一保证的是* s ++将首先访问s然后为下一个语句递增。 未定义的是&& s和&& t是否在增量之前或之后看到值…
非常挑剔点，除了其他人提出的那些：
如果a和b都是0长度，则此例程返回NULL。 如果它应该遵循strstr的规范，那么在这种情况下它必须返回a 。 这是有道理的，因为空字符串b确实是空字符串b的子字符串。
你为什么不为你的工作使用一个function？ 你知道strstr（）吗？
const char* mystrstr(const char* a,const char* b) { size_t blen=strlen(b); while( *a ) { if( !strncmp(a,b,blen) ) return a; ++a; } return 0; }
* t = b; //杀死b的常数….
同样为了清晰的代码你可以做（ a！=’\ 0’）而不是while（* a）也是第二个while语句：while（（* s ++ == * t ++）&& * s && * t）; 将失败….尝试采取int flag =（* s ++ = * t ++）; 并做一点简化
效率？ 这太糟糕了！ <这并不意味着我可以做得更好，但是......我会做同样的事情。 ;）
看看Knuth-Morris-Pratt 。