在普通的C中,不使用strlen或任何使用strlen的库函数,如何找到一个字符串是否包含在另一个字符串中？

Question

我说没有strlen用于效率目的.因为如果你使用strlen那么你已经迭代了一个字符串,最好的算法总是迭代一个给定的容器不超过一次.所以帮助我思考如何实现一个功能

bool contains ( char * s1, char * s2 ) 
{
   // ... 
}

尝试:

bool contains ( char * s1, char * s2 ) 
{
   // returns true or false depending on whether s1 is contained in s2

   // define that every string contains the empty string
   if ( !*s1 ) return true;

   // search for substrings of s2 that equal s1
   bool flag = true;
   while ( *s2 ) 
   {
       char * c = s1; 
       while ( *c++ == *s2++ ); 
       if ( !*c ) 
       {
          flag = true; 
          break;
       }
       else
       {
          flag = false;
       }
   }
   return flag;
} 

但是,我想做几个优化

• 如果可能的话,想摆脱它flag作为一个额外的内存字节
• 这else { flag = false; }是一个大部分时间进入的条件块,并且每次进入都会做同样的事情,所以我想以某种方式摆脱它
• 即使if ( !*s1 ) return true;早期休息有助于更优雅地编写函数的其余部分,但我讨厌在函数开头检查"一个特殊情况"条件.如果可能的话,我希望该函数能够直接进入包含所有逻辑的单个循环.
  • 该char * c = *s1在循环的每次迭代副本是一个额外的字节,这将是很好的摆脱,但我不知道如何摆脱它

我会写这个吗？

Answer 1

你真的需要自己实现吗？首先,存在可以轻松解决此问题的函数strstr,有关详细信息,请参阅此处:http://en.cppreference.com/w/c/string/byte/strstr

如果你真的需要自己实现这一点,重新发明轮子是没有意义的.有许多字符串搜索算法,最常见的三种是:

• 克努特莫里斯普拉特
• 博耶 - 穆尔
• 拉宾,卡普

每个都有自己的优点和缺点,请阅读这些链接以获取更多信息.