Как сжато регулярное выражение соответствует любой части уникальной строки?

Question

Контекст:

Скажем, у меня есть набор строк, которые все различны, хотя они могут разделить исходные последовательности, т.е. apple, banana, bpple, canana, applf.

Как лучше всего использовать регулярное выражение для строки, которая может содержать любое начальное подмножество одного из этих строк? Например, apple и banana явно совпадают. Так будет banan, ba, bp и c. b и appl были бы неоднозначными (и поэтому не должны совпадать).

Использование генерируемых классов символов в динамически созданных регулярных выражениях (медленных и уродливых), я могу создать для этого механизм соответствия. Однако сложно сказать, что, когда я пытаюсь, я в конечном итоге выполняю большую часть логики соответствия в Python/pick-your-language и reitchx. Есть ли какой-то краткий способ сделать эту работу регулярными выражениями?

Простейший способ сделать это может заключаться в том, чтобы разбить каждую возможную строку (apple, banana и т. Д.) В список и сопоставляться с каждым из них последовательно, но любопытство и упрямство заставляют меня задаться вопросом, нет ли какого-либо способа сделать это только с регулярным выражением/в основном.

TL; DR:

Есть ли способ, с помощью регулярных выражений, чтобы соответствовать: тогда и только тогда, когда строка поставляется является уникальный и левой начиная подстрока только один из заданный набор строк?

Answer 1

Не используйте регулярные выражения. Вы просите листья в trie.

Если вы абсолютно необходимо использовать регулярные выражения, то они могут быть построены следующим образом:

(a(p(p(le?)?)?)?|b(a(n(a(na?)?)?)?)? ...) 

Легко написать код, который строит, но вы не сможете узнать, что фактически соответствует (например, пользователь вводит «приложение»), вы, вероятно, хотите знать, что это соответствует «яблоку»). Также, изменяя это, чтобы убедиться, что не более один матч действительно громоздкий. Код, который создает регулярное выражение, будет намного сложнее, чем просто создание trie (на самом деле вам, вероятно, нужно создать нечто, эквивалентное trie, чтобы создать регулярное выражение, которое вы просите).