2. You are given two strings A and B of the same length. Each string contains N lower case latin
characters (from 'a' to 'z'). A shift operation will remove the first character of a string and add the same
character at the end of that string. For example, after you perform a shift operation on a string 'abed', the
new string will be "beda'. If you perform this operation two times, the new string will be 'dab'. Use the
KMP algorithm to show that the two strings are rotations of each other. Provide the runtime of your
algorithm.
Tries or Strings (25 Pts)
Rubric: (roughly the following points should be covered )
Provide the data structure and explain how you would save the queries, count, insert into that data
structure , and read. Also mention the runtime.