c - 在纯 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; }是一个大多数时候都会输入的条件 block ，每次输入时都会执行相同的操作，所以我想以某种方式摆脱它
• 尽管 if ( !*s1 ) return true;早期中断有助于更优雅地编写函数的其余部分，我讨厌在函数开头进行“一个特殊情况”条件检查。如果可能的话，我希望该函数能够直接开始进入包含所有逻辑的单个循环。
  • char * c = *s1循环的每次迭代中的复制都是一个额外的字节，很高兴摆脱它，但我不知道如何摆脱它

那我会写这个吗？

Answer 1

你真的需要自己实现这个吗？首先，有一个函数 strstr 可以轻松地为您解决这个问题，请参阅这里了解更多信息:http://en.cppreference.com/w/c/string/byte/strstr

如果您确实需要自己实现此功能，则没有必要重新发明轮子。有许多可用的字符串搜索算法，最常见的三种是:

• Knuth-Morris-Pratt
• Boyer-Moore
• Rabin-Karp

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