c - 在一个数组中查找另一个数组

Question

我们有两个数组

char A[]="ABABABABBBABAB";

另一个是

char B[]="BABA";

如何在 A 中找到 B 以及每次出现时它的起始位置和结束位置？

例如这个

Between 2-5
Between 4-7
Between 10-13

Answer 1

是的，您可以使用strstr函数来做到这一点。

This function returns a pointer to the first occurrence in haystack of any of the entire sequence of characters specified in needle, or a null pointer if the sequence is not present in haystack.

所以你会发现指针指向字符串的开头。但话又说回来，如果您想找到下一次出现的情况，您将相应地更改第一个参数，忽略找到第一次出现的部分。一个简单的说明:-

   char haystack[]="abismyabnameab";
   char needle[]="ab";
   char *ret;
   ret = strstr(haystack, needle);
   while(ret != NULL){
      /* do work */

      printf("%s (%zu,%zu)\n",ret, ret-haystack, ret-haystack+strlen(needle)-1 );
      ret = strstr(haystack+(ret-haystack)+1,needle);
   }   

我省略了获得这些计数的部分，它吐出针的索引。作为提示，请注意一件事 - 您将知道针的长度以及它从哪里开始，您可以使用 strstr 知道。 (ret - haystack 专门针对 haystack 中 needle 的每个实例)。

请注意，此插图代码显示了其内部不重复出现的字符串的示例。例如，在BBBBB中找到BB，那么我们将找到每个位置的所有出现。但上面的解决方案跳过了第二次出现。一个简单的修改是添加到 haystack 1 以在字符串中搜索比上一次迭代晚一个字符的字符串。

更好的解决方案是使用 KMP 查找故障函数。这将提供更好的复杂性解决方案。 O(n+m)。但在之前的情况下，它是O(n*m)。