Advanced Data Structure and Application Example of String Reduplication Using bitmap
- 2021-06-28 12:49:31
- OfStack
bitmap is an array of single elements boolean (0/1, 0 for nonexistent, 1 for present).
If C/C++ does not have a native boolean type, int or char can be used as bitmap if we want to determine if a character (char) has ever occurred
Using int as the underlying data structure of bitmap, bitmap is an int array, with an int length of 32 bit bits.
c / 32 ⇒Number of ints in bitmap c% 32 ⇒The number of bit bits in an int in bitmap;Using char as the underlying data structure of bitmap, bitmap is the char array, and one char is 8 bit bits long.
c / 8 ⇒Number of chars in bitmap c% 8 ⇒The number of bit bits in an char in bitmap;ASCII
A-Z:65-90 a-z:97-122If you use char as an alternative underlying data structure to bitmap, what length does char need to be in order to achieve string redundancy?122/8+1 &868658;16.If int is used as the underlying implementation of bitmap, the length of the int array is 122/32 + 1 ⇒4
1. int as the underlying data structure
void dedup(const char* src, char* dst)
{
unsigned int exists[4] = { 0 };
int i = 0, j = 0;
unsigned int mask;
char c;
while (src[i])
{
c = src[i];
mask = 1 << (c % 32);
if ((exists[c / 32] & mask) == 0)
{
dst[j++] = c;
exists[c / 32] |= mask;
}
i++;
}
dst[j] = '\0';
}
2. Use char as the underlying data structure
void dedup(const char* src, char* dst)
{
unsigned char exists[16] = { 0 };
int i = 0, j = 0;
unsigned int mask;
char c;
while (src[i])
{
c = src[i];
mask = 1 << (c % 8);
if ((exists[c / 8] & mask) == 0)
{
dst[j++] = c;
exists[c / 8] |= mask;
}
i++;
}
dst[j] = '\0';
}
summary