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.

Answer 1

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