szintiszta algoritmikus problema
Ebből (ha egyáltalán érvényes most a BSD grep szitura) egyáltalán nem következik, hogy "könnyű".
A konkrét probléma továbbá nem feltétlenül csak algoritmikus. Ha megnézed a freebsd wiki-ben a grep cikkelyét (valahol volt itt linkelve a témában), akkor látod, hogy specifikációs kérdések is vannak -- először is ki kellene választaniuk, hogy milyen regex változatot akarnak támogatni.
Ha jól sejtem, első körben a POSIX-ra lőttek, de hosszú távon GNU kompatibiliset szeretnének. Ha megvan a kívánt regex válfaj, akkor is rengeteg implementációs kérdés marad nyitva. Lásd például: