I first clarified the constraints and expected complexity. I explained the brute-force approach with pseudocode and then optimized it using the KMP algorithm, describing its preprocessing and search steps to achieve linear time complexity.