using memset() and memcpy() function

Question

// 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; 
}

We use two hash arrays of size 26 (for a-z, where 0 is a, and z is 25). The approach is simple, if we have seen a character before we’ll mark it and if we haven’t then ignore the character because it is not a common one. why does this code not give desired output? Whereas if I use memset(prim,true,sizeof(prim)) instead of bool prim[MAX_CHAR] = {true}; for initialization and memcpy(prim,sec,MAX_CHAR) instead of for(int k=0;k<n;k++) prim[k] = sec[k]; for copying the boolean array sec[] in prim[] it works just fine.

https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h — , Feb 07 '19 at 18:33
As well as https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice — Some programmer dude, Feb 07 '19 at 18:34
As an aside, neither `#include ` or `using namespace std;` is considered good practice — AndyG, Feb 07 '19 at 18:35
Depending on your compiler and settings of it, you might be building the source in C++03 mode, in which case `std::string` might not contain a terminator. Always use the actual length of the string if iterating over indexes. Or better yet use iterators. Or even more better us a [range `for` loop](https://en.cppreference.com/w/cpp/language/range-for). — Some programmer dude, Feb 07 '19 at 18:36
Regarding that commented out `memset` call, in the generic case use [`std::fill`](https://en.cppreference.com/w/cpp/algorithm/fill) instead. And [`std::copy`](https://en.cppreference.com/w/cpp/algorithm/copy) instead of `memcpy`. — Some programmer dude, Feb 07 '19 at 18:39

bruno · Accepted Answer · 2019-02-07T22:31:02.783

Warning

bool prim[MAX_CHAR] = {true};

is not equivalent to memset(prim, true, sizeof(prim));

MAX_CHAR is 26, and you only give 1 value with {true}, so prim[0] is initialized with true and all the 25 next entries are initialized with 0 (false). true is not used up to the end of the array.

But

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 }

initializes the 26 entries (if I count well)

Of course memcpy(prim,sec,MAX_CHAR) and for(int k=0;k<n;k++) prim[k] = sec[k]; are not equivalent because n is the number of strings (4) and doesn't value MAX_CHAR (26)

Execution with your code :

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

Execution with memset or the 26 true in {}, and replacing for(int k=0;k<n;k++) by for(int k=0; k<MAX_CHAR; k++) :

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

A proposal from François Andrieux (in a removed remark below) to remove the problem about the initialization of prim : reverse the boolean value in prim, so

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'); 
}

Execution :

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

But the reverse logic for prim and the standard logic for sec can be confusing

Thank you for clarification on initialization mistake but still the expected output is `e g k s` **common characters** So the answer for use of `memcpy(prim,sec,MAX_CHAR)` instead of `for(int k=0;k — Akshat mahla, Feb 07 '19 at 20:22
@Akshatmahla I edited my answer to speak about that and correct the code, but frankly _n_ valuing the number of strings (4) obviously `for(int k=0;k — bruno, Feb 07 '19 at 22:31

using memset() and memcpy() function

1 Answers1