It's libregex, but with a different name.

You can use either, provided you change the Makefile to use the matching name, -lgnurx or -lregex.

gnurx from MinGW on sourceforge
regex from GnuWin32 on sourceforge