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: %d\n", 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 %d\n",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 %d\n", 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

在valgrind下执行

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();