Algorithm Design & Analysis Questions

1. In a string, we can have repeated pattern. Example:

Input	Output
abc	none
abaa	none
aaaa	(a) 4
abab	(ab) 2
abcabc	(abc) 2
ababacababac	(ab) 2
ababacababacababac	(ababac) 3

The problem:

• Input: a string in a line.
• Output: Print the pattern and the repeated count if there is a repeated pattern, Print "none" otherwise.
• Task: Design an algorithm in code C/C++ to for the problem and write down the Algorithm analysis. The complexity of the algorithm must be in O(n).
• PS: Use the KMP algorithm for string matching. The repeated pattern is valid only from the first character.

P.S:

- Please answer in a proper format - Please answer in a typed or softcopy format - Please don't do it with pen or pencil, do it with software or tools - If you want to ask any question, ask it in the comment section, I will try to answer it

Thanks!