The longest common sub sequence, satisfying a given pattern L, between two strings A and B. It uses basic finite automata manipulation and longest path algorithm.

Problem setup: Input: two strings A, B, along with a regular expression L Output: a string C satisfying all of the following: 1. C is a sub sequence of A 2. C is a subsequence of B 3. C is in L 4. C is longest satisfying 1, 2, 3.

You may use the following to test your code: input: A is the string abaacbababba B is the string bbbacababcba L is the regular expression ab(bb)*a

Output: C is abbba

Assume that the alphabet on all automata and languages is {a,b,c}.

write a Python3 code to solve this problem, code MUST able to run those test cases correctly.