子字符串搜索面试问题

如果a指向“cat”,b指向“a b”,func将返回一个指向“a t”(错误值)的指针,而不是0(预期值),因为指针t是递增的,即使比较(*s++==*t++)失败。

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

我不是C开发人员,因此我不能也不会对代码的正确性发表评论,但在效率方面,请参阅:

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

我相信你有一个天真的搜索版本。看看Knuth-Morris-Pratt算法。你可以在绳子上做些小的工作 b 在你搜索之前 a . 然后你可以在 O(|a|+|b|) . 和 |b| 大于 |a| 然后 乙 不能在 一 所以它变成了 O(|a|) .

关键是如果 一 是:

abcabe

和 乙 是:

aba

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

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

哪个是 O(|a|*|b|) 字符,但仅限于等于 O(αa)

是啊。。。

• 不能将B指定为它的销毁常量。
• 它与“b”中的最后一个字符不匹配。

嗯,它确实有一个小问题,那就是它实际上不起作用。

尝试使用a=“xyz”和b=“xw”运行。当你第一次点击while循环时,x=x,你增加两个指针,然后再次循环。然后Y!=w,所以退出循环。但是您已经增加了指针,所以t==0,并且报告了一个命中。

通常,无论最后一个字符是否匹配,都会报告命中。

如果b是一个1个字符的字符串,那么最后一个字符是唯一的字符,因此1个字符的字符串匹配任何内容。

我建议不要尝试用带有副作用的单个语句来完成循环。如本例所示,这很棘手。即使你做对了,对于那些试图阅读你的代码的人来说,这也是非常神秘的。

可以将“while loop”重写为(不使用标志):

while( (*s == *t) && *s && *t ){
  s++;
  t++;
}

或用于循环…下面的代码是从“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 如果没有正确地终止空值,函数将可怕地死亡。
• 如果 b 未正确终止空值,该函数可能会死机。
• 凹痕很奇怪。

这是要做的工作,但我有更好的方法做这件事。 检查本文: http://en.wikipedia.org/wiki/String_searching_algorithm

我想是这样的:

while( (*s++ == *t++) && *s && *t );

未定义,因为您在后增量之后访问变量,它们可能在增量之前或增量之后。

除非他们改变了它,否则表达式的副作用在标准中是不确定的。唯一保证的是,*S++将首先访问S,然后为下一条语句递增。未定义的是&S和&T是否查看增量之前或之后的值…

非常挑剔的一点,除了其他人提出的:

如果 a 和 b 都是0长度,则此例程返回空值。如果它应该遵循 strstr ,那么它必须返回 一 那样的话。这是有意义的,因为空字符串 乙 确实是空字符串的子字符串 一 .

你为什么不在工作中使用函数?你知道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语句: 同时((*S++==*T++)&&*S&&*T); 将失败….尝试获取int标志=(*s++=*t++); 做一点简化

效率如何?太可怕了!这确实是 不 意思是我可以做得更好,尽管…我也会这么做的。;)

看一看 Knuth-Morris-Pratt .