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

Вот решение 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();

Answer 2

сравнения в

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