What is an efficient algorithm for regex **search** all occurrences (starting indexes) of a pattern in a long string?↵
↵
↵
↵
↵
Say I only have * in this question: https://leetcode.com/problems/regular-expression-matching/↵
↵
↵
a* search in aaa returns [0, 1, 2]↵
↵
a*b search in abb [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
↵
↵
↵
↵
Say I only have * in this question: https://leetcode.com/problems/regular-expression-matching/↵
↵
↵
a* search in aaa returns [0, 1, 2]↵
↵
a*b search in abb [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
