JAVA Implement and test:

• CODE Constructing the DFA for KMP substring search (page 766)
• Modify the program to trace the execution like below:
• Show the parameters pat
• Show all the non zero assignments to dfain the format: dfa['A'][3] = 4
• In the for-j loop show x and j, and the j-th character in the patterncharacter
• In thefor-c loop
• show c
• show the dfaassignment
• Show the new x value
• At the end show the entire matrix
• Test the algorithm with 5representative strings, showing the trace and the result

\f