You will be given a set of string called T={T1,T2,....,Tk} and another string called P . You will have to find the number of occurrences of P in T . And to do that, you will have to build a string matching automaton. The strings will contain only small letters from the English alphabet from a to z . If the length of the pattern P is m , then your automaton will have m+1 state labelled by 0,1,2,.....,m . Each of these states will have 26 state transitions.
- Create an (m+1)ร26 state transition table. ( coding )
- Feed the strings Ti to the automaton and see how many times P occur in Ti for all i . ( coding )
- Compute the total time and space complexity for your solution in terms of n,m,k given that the maximum length of a string in T is n . ( complexity analysis )