Apologies.
I thought the question was about just checking for palindrome.
On 6/6/10, Antony Vincent Pandian.S. <sant...@gmail.com> wrote:
> Follow hare and tortoise algorithm.
>
> For even length,
> once the traversal through out the string is done, move the fast
> pointer to slow pointer +1 location and start iterating for (length/2)
> times with 2 indices. One indice increasing for fast pointer and the
> other for slow pointer. Keep checking the value at slow pointer index
> and fast pointer index. If they are different, it is not a palindrome.
> eg: for string of length 6 with index starting from 0, by hare and
> tortoise method, slow pointer is placed at 2 while fast pointer is
> placed at 4. Move the fast pointer to (index of slow pointer)+1. In
> this case, move it to 3. Start traversing the slow pointer in
> decreasing manner while increasing the fast pointer.
>
> For odd length,
> follow hare and tortoise method. Move the fast to the slow pointer
> index which is also the middle of the string, start incrementing one
> pointer while decreasing the other and comparing the values of each
> index.
>
> Complexity is O(2n)
>
> On 6/5/10, Bharath <bharath1...@gmail.com> wrote:
>> Complexity is O(n3) for both above solutions
>>
>> Ex: aaaaaaaa
>>
>> On Sat, Jun 5, 2010 at 3:27 AM, Minotauraus <anike...@gmail.com> wrote:
>>
>>> for(int i=0; i<word.length-1; i++)
>>> {
>>> if(word[i]==word[i+1]) //for an even palindrome, consecutive letters
>>> at the middle of the string have to be the same
>>> {
>>> palindromeFound=true;
>>>
>>> while(n>0&&m<word.length) //once you've found the middle of
>>> the palindrome, compare left of and right of, while making sure you
>>> don't go out of bounds
>>> {
>>> if(word[n--]==word[m++])
>>> {
>>> startIndex = n; //overwrite index of the
>>> start and end locations
>>> endIndex = m;
>>>
>>> }
>>> else break;
>>> }
>>> }
>>> }
>>>
>>> print("Even length-ed Palindrome: "+word[startIndex->endIndex], length
>>> = endIndex-startIndex);
>>>
>>> Complexity =O(n).
>>>
>>> On Jun 5, 2:34 am, Satya <satya...@gmail.com> wrote:
>>> > Hi,
>>> >
>>> > How to find largest palindrome, which is even in length in a string.
>>> > Complexity should be "lessthan" O(n^2).
>>> >
>>> > Ex;- abacbbcababac - Given string.
>>> > 'abacbbcaba' - is the largest even length palindrome.
>>> >
>>> > Thanks,
>>> > Satya
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>
>>
>> --
>> <<Bharath>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
> --
> Sent from my mobile device
>
> Luv,
> S.Antony Vincent Pandian
>
--
Sent from my mobile device
Luv,
S.Antony Vincent Pandian
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
