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

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 pseudocode/code to for the problem and write down the Algorithm analysis. The complexity of the algorithm must be in O(n).

PS: You use the algorithm for string matching taught in class. The repeated pattern is valid only from the first character.

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