3. 1. Prove that the naive string matching algorithm runs in time O(n) when all the characters in the pattern P are different. 4. We say that P occurs circularly in T if we can partition P to two...

3.

1. Prove that the naive string matching algorithm runs in time O(n) when all the characters in the pattern P are different.

4. We say that P occurs circularly in T if we can partition P to two strings A, B such that A is a suffix of T and B is a prefix of T. Example: T = abaacacaab, P = aabab. P occurs circularly in T because of the partition A = aab and B = ab. Let T be a string of length n and P be a string of length m < n.="" design="" an="" o(n)="" time="" algorithm="" for="" deciding="" whether="" p="" occurs="" circularly="" in="">