정규표현식을 통해 파일의 이름 검색

[개발 환경]
- 우분투 13.10
- C언어

[자료구조]
struct finfo
{
char filename[4096];
+
파일의 정보들...
};

- 자료는 디렉터리의 경로를 주면 그 하위까지 자료들이 저장

- 정규 표현식을 통해 저장된 자료들의 파일 이름을 비교해서 일치할 경우 파일 이름과 정보들을 출력
이러한 프로그램입니다.

프로그램 구현은

1. 자료들을 단일 연결 리스트로 저장
2. 정규 표현식을 regcomp라는 함수로 컴파일
3. regexec로 컴파일된 정규식과 파일의 이름을 비교
4. 일치할 경우 파일의 이름과 정보를 출력
5. 3, 4번을 연결 리스트의 끝까지 반복

이러한 구조로 구현하였는데 이럴 경우 자료들의 개수가 증가할수록 비교 횟수도 증가하여서 검색 성능이 떨어지는 거 같습니다.

[질문]
1. 모든 자료를 순차적으로 비교하는 방법 말고는 없는지 궁금합니다
2. regexec라는 함수가 내부적으로 정규 표현식과 파일의 이름을 비교할때 어떤 알고리즘을 이용해서 문자열의 패턴을 비교하는지 궁급합니다.
(AC, KMP, BM 등...)