A palindrome is a string that's the same forward as it is backwards. Examples include a,...

Transcribed Image Text:

A palindrome is a string that's the same forward as it is backwards. Examples include "a", "racecar", "hannah", "rats live on no evil star", 6699 The algorithm below takes in a string and returns the length of the longest prefix of the string that's a palindrome. Example input-output pairs include ("apple", 1), ("attack", 4), ("racecar", 7) Find a tight bound (O) on the runtime (number of steps) of the following algorithm: palindrome_prefix (s) length(s) 1. n 2. current_best 0 3. for i 1 to n 4. 5. 6. 7. 8. 9. 10. return current_best Note: s[i] means the ith character from string s. is_palindrome ← true for j1 to i: if s[j] s[i+1−j] then is_palindrome ← False if is-palindrome then current_best i A palindrome is a string that's the same forward as it is backwards. Examples include "a", "racecar", "hannah", "rats live on no evil star", 6699 The algorithm below takes in a string and returns the length of the longest prefix of the string that's a palindrome. Example input-output pairs include ("apple", 1), ("attack", 4), ("racecar", 7) Find a tight bound (O) on the runtime (number of steps) of the following algorithm: palindrome_prefix (s) length(s) 1. n 2. current_best 0 3. for i 1 to n 4. 5. 6. 7. 8. 9. 10. return current_best Note: s[i] means the ith character from string s. is_palindrome ← true for j1 to i: if s[j] s[i+1−j] then is_palindrome ← False if is-palindrome then current_best i

Answer rating: 100% (QA)

outer loop iterates i values from 1 to n and for each o... View the full answer