Palindrome

A palindrome is a finite string equal to its reversal. For example, the strings $010$ and $0110$ are palindromes.

Decide whether a finite string is a palindrome by comparing corresponding symbols from opposite ends. The test needs at most half as many symbol comparisons as the string length and can use constant auxiliary space.