ccc.cpp

ccc.cpp

    // g++ -o ccc ccc.cpp 
    // ./ccc 'a' 'aacb' && echo 'YES' || echo 'NO'
    #include <iostream>
    #define ENDSTRING '\0'
    #define DOTCHAR '.'
    #define STARCHAR '*'
    int regex(char *str, char* pattern) {

        // We are gonna use the C++ pointer arithmetic to go forward through our strings.
        // #Pointer #PointerArithmetic 
        //    
        // String is a array of char (or char* or char str[]), we have 2 pointers
        // str => pointer to the first character of the "string"
        // pattern => pointer tp the first character of the "pattern"

        // [A,P,A,T,*,N,\0]
        //  ^-- char* pattern = &argv[1][0] =>   
        
        // this allows us to travers the String only with theses 2 pointers 
        
        // [A       ,P      ,A      ,T      ,*      ,N      ,\0]
        //  0x0010   0x0018  0x0020  0x0028  0x0030  0x0038   0x0040
        //  ^-- *(pattern)  
        
        // [A       ,P      ,A      ,T      ,*      ,N      ,\0]
        //  0x0010   0x0018  0x0020  0x0028  0x0030  0x0038   0x0040
        //           ^-- *(pattern+1) 

        // [A       ,P      ,A      ,T      ,*      ,N      ,\0]
        //  0x0010   0x0018  0x0020  0x0028  0x0030  0x0038   0x0040
        //                   ^-- *(pattern+2) 
        
        while(*pattern != ENDSTRING && *str != ENDSTRING) { // While we don't reach the end of our string or pattern
            bool match = *str == *pattern || *pattern == DOTCHAR; // Doest it match ?
            pattern+=1; // Pointer of pattern + 1 (so point to next character)
            if(*pattern == STARCHAR) { /// if we encounter a '*', need to take care of repetition
                
                // Managing 'XX.*XX' in the pattern to not be too greedy and be sure it match end of the string after the '.*'  
                // example : pattern = 'a.*b',  string = 'aab'   
                // This means '.*' increase the time big O of the algo
                if( *(pattern-1) == DOTCHAR && regex(str+1,pattern+1)==0) {
                    return 0;
                }
                
                // if the character was matching, pattern come back to previous character (as next can be same ) and string pointer goes to the next character
                if(match) {
                    pattern -=1;
                    str +=1;
                } else { // otherwise, it means '*' reach the end, we need to test next character of the pattern (as * means 0 or more)
                    pattern+=1;
                }
            } else { // if next character isn't a '*' (so normal character)
                if(match) { // if there was a match, then check next character of the string
                    str +=1;
                } else { // otherwise the pattern and string doesn't match we can stop
                    return 1;
                }
            }
        }
        if(*pattern != ENDSTRING && *(pattern+1)==STARCHAR) { // extra check in case we got a '*' at the end of the pattern
            pattern+=2;
        }
        return !((*pattern) == (*str));
    }
    int main(int argc, char *argv[]) {
        
        // [A,P,A,T,*,N,\0]
        //  ^-- &argv[1][0] => pattern 
        
        char* pattern = &argv[1][0]; 
        // [A,S,T,R,I,N,G,\0]
        //  ^-- &argv[2][0] => str 
        char* str = &argv[2][0];

        return regex(str,pattern);
    }