Реализация Regex, которая может обработать сгенерированный машиной regex's: *не отслеживающий в обратном порядке*, O (n)?

Consider how DFAs are created from regular expressions:

You start with a regular expression. Each operation (concat, union, Kleene closure) represents a transition between states in an NFA. The resulting DFA's states represent power sets of the states in the NFA. The states in the NFA are linear to the size of the regular expression, and therefore the DFA's states are exponential to the size of the regular expression.

So your first constraint,

have a worst case time-complexity of regex evaluation of O(m*n) where m is the length of the regex, and n the length of the input

Is impossible. The regex needs to be compiled to a 2^m-state DFA (worst case), which won't be done in linear time.

This is always the case with all but the simplest regular expressions. Ones that are so simple you can just write a quick .contains expression more easily.

Если вы можете справиться с использованием небезопасного кода (и проблемы с лицензированием), вы можете взять реализацию из этого порта Windows TRE .

Возможно, вы сможете использовать это непосредственно с помощью P / Invoke и явных структур макета для следующего:

typedef int regoff_t;
typedef struct {
  size_t re_nsub;  /* Number of parenthesized subexpressions. */
  void *value;     /* For internal use only. */
} regex_t;

typedef struct {
  regoff_t rm_so;
  regoff_t rm_eo;
} regmatch_t;


typedef enum {
  REG_OK = 0,       /* No error. */
  /* POSIX regcomp() return error codes.  (In the order listed in the
     standard.)  */
  REG_NOMATCH,      /* No match. */
  REG_BADPAT,       /* Invalid regexp. */
  REG_ECOLLATE,     /* Unknown collating element. */
  REG_ECTYPE,       /* Unknown character class name. */
  REG_EESCAPE,      /* Trailing backslash. */
  REG_ESUBREG,      /* Invalid back reference. */
  REG_EBRACK,       /* "[]" imbalance */
  REG_EPAREN,       /* "\(\)" or "()" imbalance */
  REG_EBRACE,       /* "\{\}" or "{}" imbalance */
  REG_BADBR,        /* Invalid content of {} */
  REG_ERANGE,       /* Invalid use of range operator */
  REG_ESPACE,       /* Out of memory.  */
  REG_BADRPT            /* Invalid use of repetition operators. */
} reg_errcode_t;

Затем используйте экспорт, способный обрабатывать строки со встроенными нулями (с поддержкой широкого диапазона символов)

/* Versions with a maximum length argument and therefore the capability to
   handle null characters in the middle of the strings (not in POSIX.2). */
int regwncomp(regex_t *preg, const wchar_t *regex, size_t len, int cflags);

int regwnexec(const regex_t *preg, const wchar_t *string, size_t len,
      size_t nmatch, regmatch_t pmatch[], int eflags);

В качестве альтернативы оберните его через решение C ++ / CLI для упрощения перевода и т. д. гибкость (я бы определенно предположил, что это разумно, если вам комфортно с C ++ / CLI).

Где я могу найти надежно быструю реализацию Regex?

Вы не можете.

Кто-то должен это сказать, ответ на этот вопрос с учетом ограничений: конечно, вы не можете - маловероятно, что вы найдете реализацию, соответствующую вашим ограничениям.

Кстати, я уверен, что вы уже пробовали это, но скомпилировали ли вы регулярное выражение (с опцией, которая выводит в сборку) - я говорю, потому что:

если у вас сложное регулярное выражение и миллионы коротких строк для тестирования

Быстрый комментарий: То, что вы можете моделировать построение DFA, имитируя несколько состояний, не означает, что вы не выполняете работу по преобразованию NFA-DFA. Разница заключается в том, что вы распределяете усилия по самому поиску. Т.е. в худшем случае производительность остается неизменной.