How to efficiently implement regular expression like .*a.*b.*?

I want to matching of filenames like Colibri does. I tried to solve it by regular expressions.

Searching in Colibri works that You type characters which are in order inside of a filename and it finds all files with these characters in order in the filename. For example for "ab" it finds "cabal", "ab", and "achab".

Simple insertion of .* between letters works (so searched string "ab" becomes regular expression .*a.*b.*), but I want to make it on large amount of files.

So far I have O(N*???), where N is amount of filenames and ??? is at best linear complexity (I assume my language uses NFA). I don't care about space complexity that much. What data structures or algorithms should I choose to make it more efficient (i开发者_JAVA技巧n time complexity)?

If you just want to check whether the characters of a search string search are contained in another string str in the same order, you could use this simple algorithm:

pos := -1
for each character in search do
    pos := indexOf(str, character, pos+1)
    if pos is -1 then
        break
    endif
endfor
return pos

This algorithm returns the offset of the last character of search in str and -1 otherwise. Its runtime is in O(n) (you could replace indexOf by a simple while loop that compares the characters in str from pos to Length(str)-1 and returns either the offset or -1).

It will greatly improve your efficiency if you replace the . with a character negation. i.e.

 [^a]*a[^b]*b.*

This way you have much less backtracking. See This Reference

Edit* @yi_H you are right, this regex would probably serve just as well:

a[^b]*b

Your . is unnecessary. You'll get better performance if you simply transform "abc" into ^[^a]*a[^b]*b[^c]*c.

string exp = "^";
foreach (char c in inputString)
{
   string s = Regex.Escape (c.ToString()); // escape `.` as `\.`
   exp += "[^" + s + "]*" + s; // replace `a` with `[^a]*a`
}
Regex regex = new Regex (exp, RegexOptions.IgnoreCase);
foreach (string fileName in fileNames)
{
   if (regex.IsMatch (fileName))
      yield return fileName;
}

For a limited character-set it might make sense to create lookup table which contains an array or linked list of matching filenames.

If your ABC contains X characters then the "1 length" lookup table will contain X table entries, if it is a "2 length" table it will contain X^2 entries and so on. The 2 length table will contain for each entry ("ab", "qx") all the files which which have those letters in that order. When searching for longer input "string" look up the appropriate entry and do the search on those entries.

Note: calculate the needed extra memory and measure the speed improvement (compared to full table scan), the benefits depend on the data set.