GCC 3.4.5 is fine... In its default installation, MinGW does not include a regex library, so you need to install one by yourself, such as this MinGW Port.
To install, just unzip the contents of the bin and dev packages into your MinGW folder.
To compile your C/C++ applications with the regex library, you need to append -lregex to your gcc command, as in:
g++ -o rex rex.cpp -lregex