Recently, I have been working on an algorithm to find the longest palindrome in a string (ignoring spaces & case-insensitive). I have been using Ruby, and I have developed this windowing search algorithm .
My question is: Is there a faster way to find the longest palindrome in a string (on a non-specific case basis)?
def longest_palindrome(input)
string = input.gsub(" ","") # remove white spaces
string.downcase! # convert to lowercase
length = string.length
search = length - 1 # search window size
while search > 0 # search while chars > 2
for i in 0..(length-search) # search every window
sub = string[i..(search+i)] # check substring
return sub if is_palindrome?(sub)
end # return asap once found
search -= 1 # dec. window size by 1
end
return false # false if none found
end
def is_palindrome?(string)
return false if string.length < 2 # false if 1 character
array = string.chars
n = array.length-1 # last string index
for i in 0..(n/2) # check if whole string
return false if array[i] != array[n-i] # check if mirror image
end
return true # true if all tests pass
end
