Pencocokan ekspresi reguler waktu linear penuh

Apakah ada algoritma untuk memeriksa apakah ukuran ekspresi reguler cocok dengan string ukuran , dengan asumsi alfabet ukuran tetap jika itu penting?$O(n+m)$$n$$m$

Algoritma NFA standar adalah kasus terburuk . Groz et al. mencapai waktu linier untuk berbagai kelas ekspresi reguler, tetapi tidak semua. Apakah ada hasil yang lebih baik?$O(nm)$

Groz, B., Maneth, S., & Staworko, S. (2012, Mei). Ekspresi reguler deterministik dalam waktu linier.

Groz et al. nyatakan secara eksplisit bahwa algoritma yang paling dikenal untuk ekspresi reguler umum (pada 2012) adalah , karena Bille dan Thorup 2009, doi: 10.1007 / 978-3-642-02927-1_16 ( pracetak ).$O(nm(\log\log n)/(\log n)^{3/2}+n+m)$

Untuk alfabet ukuran tetap, Sebastian Maneth menunjukkan kepada saya bahwa dimungkinkan untuk ekspresi reguler deterministik dengan membuat Glushkov DFA: setiap posisi dalam ekspresi reguler adalah satu keadaan, dan transisi ditentukan oleh set yang dibatasi simbol yang mungkin muncul sebelum pindah ke suatu posisi. Namun, tanpa memperbaiki ukuran alfabet, itu tetap menyatakan bahwa "menemukan waktu$O(n+m)$$O(m+n)$