используя функцию memset () и memcpy () - PullRequest
Новая
       38

используя функцию memset () и memcpy ()

0 голосов
/ 07 февраля 2019 
// CPP Program to find all the common characters 
// in n strings 
#include <bits/stdc++.h> 
using namespace std; 

const int MAX_CHAR = 26; 

void commonCharacters(string str[], int n) 
{ 
  // primary array for common characters 
  // we assume all characters are seen before. 
  bool prim[MAX_CHAR] = {true}; 
  //memset(prim, true, sizeof(prim)); 

  // for each string 
  for (int i = 0; i < n; i++) { 

    // secondary array for common characters 
    // Initially marked false 
    bool sec[MAX_CHAR] = { false }; 

    // for every character of ith string 
    for (int j = 0; str[i][j]; j++) { 

      // if character is present in all 
      // strings before, mark it. 
      if (prim[str[i][j] - 'a']) 
        sec[str[i][j] - 'a'] = true; 
    } 

    // copy whole secondary array into primary 
    //memcpy(prim, sec, MAX_CHAR); 

    for(int k=0;k<n;k++)
      prim[k] = sec[k];
  } 


  // displaying common characters 
  for (int i = 0; i < 26; i++) 
    if (prim[i]) 
      printf("%c ", i + 'a'); 
} 

// Driver's Code 
int main() 
{ 
  string str[] = { "geeksforgeeks", 
                   "gemkstones", 
                   "acknowledges", 
                   "aguelikes" }; 
  int n = sizeof(str)/sizeof(str[0]); 
  commonCharacters(str, n); 
  return 0; 
}

Мы используем два хеш-массива размером 26 (для az, где 0 - это a, а z - 25).Подход прост, если мы видели символ до того, как мы его пометим, а если нет, то игнорируем символ, потому что он не является обычным.почему этот код не дает желаемого результата?Принимая во внимание, что если я использую memset(prim,true,sizeof(prim)) вместо bool prim[MAX_CHAR] = {true}; для инициализации и memcpy(prim,sec,MAX_CHAR) вместо for(int k=0;k<n;k++) prim[k] = sec[k]; для копирования логического массива sec [] в prim [], все будет работать отлично.

1 Ответ

0 голосов
/ 07 февраля 2019

Предупреждение 

bool prim[MAX_CHAR] = {true};

не эквивалентно memset(prim, true, sizeof(prim));

MAX_CHAR равно 26, и вы даете только 1 значение с {true}, поэтому prim[0] инициализируется с true и все 25 следующих записей инициализируются 0 ( false ). true не используется до конца массива.

Но 

bool prim[MAX_CHAR] = {true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true }

инициализирует 26 записей (если я считаю хорошо)

Конечно, memcpy(prim,sec,MAX_CHAR) и for(int k=0;k<n;k++) prim[k] = sec[k]; не эквивалентны, потому что n является числом строк (4) и не имеет значения MAX_CHAR (26)

Выполнение с вашим кодом:

pi@raspberrypi:/tmp $ ./a.out
pi@raspberrypi:/tmp $

Выполнение с memset или 26 true in {} и заменой for(int k=0;k<n;k++) на for(int k=0; k<MAX_CHAR; k++): 

pi@raspberrypi:/tmp $ ./a.out
e g k s pi@raspberrypi:/tmp $

Предложение от Франсуа Андрие (в удаленном замечании ниже) об устранении проблемы с инициализацией prim : обратное логическое значение в prim , поэтому 

void commonCharacters(string str[], int n) 
{ 
  // primary array for common characters 
  // we assume all characters are seen before. 
  // (false means seen before, reverse logic)
  bool prim[MAX_CHAR] = {false}; 

  // for each string 
  for (int i = 0; i < n; i++) { 

    // secondary array for common characters 
    // Initially marked false (standard logic)
    bool sec[MAX_CHAR] = { false }; 

    // for every character of ith string 
    for (int j = 0; str[i][j]; j++) { 

      // if character is present in all 
      // strings before, mark it. 
      if (!prim[str[i][j] - 'a']) 
        sec[str[i][j] - 'a'] = true; 
    } 

    // copy negation of whole secondary array into primary         
    for(int k=0; k<MAX_CHAR; k++)
      prim[k] = !sec[k];
  } 

  // displaying common characters 
  for (int i = 0; i < 26; i++) 
    if (!prim[i]) 
      printf("%c ", i + 'a'); 
}

Исполнение: 

pi@raspberrypi:/tmp $ ./a.out
e g k s pi@raspberrypi:/tmp $

Но обратная логика для prim и стандартная логика для sec могут сбивать с толку

...