Topic — Repeated Substring Pattern
Q. Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.
Explanation: It's the substring "ab" twice.
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)
Specifically for me, I learned and understood the concept of Knuth–Morris–Pratt algorithm(KMP algorithm) before going to solve the above question.
This above algorithm works for string searching for some regular pattern. After understanding the concept, it was easy to solve the above question.
Just add the whole string twice and cut the head and tail from the new string. And if we are able to find the existing/previous string, then we can return True, otherwise False.
Doubt? Let’s see the below code.
One line solution in Python:
Please feel free to comment, if you have any problem or doubt.
Never settle and always Hustle!!!
(Thanks for your time and do encourage me to write more by clapping.)