What is an efficient algorithm for regex search all occurrences (starting indexes) of a pattern in a long string?

Say I only have special character * in this question, which matches zero or any numbers of the preceeding characters: https://leetcode.com/problems/regular-expression-matching/

a* search in aaa returns [0, 1, 2]

a*b search in abb returns [0]

Here a* and a*b are patterns and aaa and abb are text strings to search within and text strings could be very long.

Borrowing https://leetcode.com/problems/regular-expression-matching/ I can only come up with a solution with O(N * N * M)

References:

https://codeforces.net/blog/entry/73568

https://codeforces.net/blog/entry/111380