C - 计算 2 个数组中相同元素的数量

Question

假设我们有 2 个数组：

char arr1[1024]="ABDDDABAC";
char arr2[1024]="DDDABKDDJABAJJ";

并希望确定 arr2 具有最大匹配元素数作为 arr1 的位置。例如，如果将 arr1[0] 与 arr2[2] 进行比较，则会产生 5 个匹配项，如下所示的代码。

int matches=0;
for (int i=0;i<strlen(arr2);i++){
    if (arr1[i+2]==arr2[i]){
        matches++;
    }
}
printf("matches: %dn", matches);

上面的代码返回 arr1 偏移 2 个索引时的匹配数，但不计算每个可能的偏移的匹配数，并返回导致最大匹配元素数的移位。

Answer 1

中的比较

for (int i=0;i<strlen(arr2);i++){
    if (arr1[i+2]==arr2[i]){
        matches++;
    }
}

只考虑(以昂贵的方式(arr2 的长度，没有关于 arr1 的保护，你可以用未定义的行为摆脱它

如果你想找到最大匹配数，你只需要迭代arr1中可能的偏移量并保存最佳情况，例如：

#include <stdio.h>
#include <string.h>
int main()
{
  const char * arr1 = "ABDDDABAC";
  const char * arr2 = "DDDABKDDJABAJJ";
  size_t max = 0;
  const char * pmax;
  size_t ln1 = strlen(arr1);
  size_t ln2 = strlen(arr2);
  for (const char * a1 = arr1; *a1 ; ++a1) {
    size_t mx = 0;
    const char * p1 = a1;
    const char * p2 = arr2;
    while (*p1 && *p2) {
      if (*p1++ == *p2++)
        mx += 1;
    }
    printf("%d matches at offset %dn",mx,  a1 - arr1);
    if (mx > max) {
      max = mx;
      pmax = a1;
      if (mx == ln2)
        /* useless to continue, cannot be better */
        break;
    }
    if (--ln1 < max)
      /* useless to continue, cannot be better */
      break;
  }
  if (max == 0)
    puts("no match");
  else
    printf("max matches %d at offset %dn", max, pmax - arr1);
}

编译和执行：

pi@raspberrypi:/tmp $ gcc -g -pedantic -Wextra -Wall m.c
pi@raspberrypi:/tmp $ ./a.out
1 matches at offset 0
2 matches at offset 1
5 matches at offset 2
2 matches at offset 3
2 matches at offset 4
max matches 5 at offset 2

瓦尔格林德的处决

pi@raspberrypi:/tmp $ valgrind ./a.out
==10912== Memcheck, a memory error detector
==10912== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==10912== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==10912== Command: ./a.out
==10912== 
1 matches at offset 0
2 matches at offset 1
5 matches at offset 2
2 matches at offset 3
2 matches at offset 4
max matches 5 at offset 2
==10912== 
==10912== HEAP SUMMARY:
==10912==     in use at exit: 0 bytes in 0 blocks
==10912==   total heap usage: 1 allocs, 1 frees, 1,024 bytes allocated
==10912== 
==10912== All heap blocks were freed -- no leaks are possible
==10912== 
==10912== For counts of detected and suppressed errors, rerun with: -v
==10912== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 3)

注意：

• 代码没有假设数组的大小，这就是为什么它包含if (--ln1 < max) ...对于使用的字符串永远不会成立，所以arr1和arr2可以是argv[1]和argv[2]而不是硬编码
。
• 如果您想要所有匹配数，请删除有关 LN1 和 LN2 的所有代码

Answer 2

这是一个 C# 解决方案。我可以回家后发布C版本，但逻辑应该是一样的。

int matches = 0;
int maxMatches = 0;
int maxIndex = 0;
String[] arr1 = { "A", "B", "D", "D", "D", "A", "B", "A", "C" };
String[] arr2 = { "D", "D", "D", "A", "B", "K", "D", "D", "J", "A", "B", "A", "J", "J" };

for (int i = 0; i <= Math.Abs(arr1.Length - arr2.Length); i++)
{
    for (int j = 0; j < Math.Min(arr1.Length, arr2.Length); j++)
    {
        if ((i+j) < Math.Min(arr1.Length, arr2.Length)  &&  arr1[i + j] == arr2[j])
        {
            matches++;
        }
    }
    if(matches > maxMatches)
    {
        maxMatches = matches;
        maxIndex = i;
    }
    matches = 0;
}
Console.WriteLine("nMaximum Matches: " + maxMatches.ToString() + " at index: " + maxIndex.ToString());
Console.Read();