Find First Occurrence of Characters

From Software Engineers Wiki
Jump to: navigation, search

Find first occurrence of any character of str2 in str1.

For example, the function returns the index of 'e' which is 1.

str1 = "HelloWorld";
str2 = "aeiou";

Contents

Answer 1: Brute force

Following is O(N^2) approach.

int str_chr_str(const char *str1, const char *str2)
{
        const char *cp1, *cp2;

        for (cp1 = str1; *cp1 != '\0'; ++cp1)
                for (cp2 = str2; *cp2 != '\0'; ++cp2)
                        if (*cp1 == *cp2)
                                return cp1 - str1;

        return -1;
}

Answer 2: Use a flag

#include <stdbool.h>

int str_chr_str(const char *str1, const char *str2)
{
        bool ch_exist[256] = { 0 };
        const unsigned char *cp;

        for (cp = (const unsigned char *) str2; *cp != '\0'; ++cp)
                ch_exist[*cp] = true;

        for (cp = (const unsigned char *) str1; *cp != '\0'; ++cp)
                if (ch_exist[*cp])
                        return (const char *) cp - str1;

        return -1;
}

Answer 3: Use a bitmap (C)

If you are concerned about memory footprint than speed.

#define bit_set_define(bitmap, size) uint32_t bitmap[((size) + 31) / 32]
#define bit_set_32(bitmap, idx) do { bitmap[(idx) / 32] |= 1 << ((idx) % 32); } while (0)
#define bit_is_set_32(bitmap, idx) (bitmap[(idx) / 32] & (1 << ((idx) % 32)))

int str_chr_str(const char *str1, const char *str2)
{
        bit_set_define(bitmap, 256) = { 0 };
        const unsigned char *cp;

        for (cp = (const unsigned char *) str2; *cp != '\0'; ++cp)
                bit_set_32(bitmap, *cp);

        for (cp = (const unsigned char *) str1; *cp != '\0'; ++cp)
                if (bit_is_set_32(bitmap, *cp))
                        return (const char *) cp - str1;

        return -1;
}

Answer 4: Use a bitmap (C++)

Same as above implementation.

int str_chr_str(const char *str1, const char *str2)
{
        std::bitset<256> bitmap;
        const unsigned char *cp;

        for (cp = (const unsigned char *) str2; *cp != '\0'; ++cp)
                bitmap.set(*cp);

        for (cp = (const unsigned char *) str1; *cp != '\0'; ++cp)
                if (bitmap[*cp])
                        return (const char *) cp - str1;

        return -1;
}
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox