Re: [algogeeks] Largest even length palindrome in a string!!
Apologies.
I thought the question was about just checking for palindrome.
On 6/6/10, Antony Vincent Pandian.S. 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 wrote:
>> Complexity is O(n3) for both above solutions
>>
>> Ex:
>>
>> On Sat, Jun 5, 2010 at 3:27 AM, Minotauraus wrote:
>>
>>> for(int i=0; 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>> 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 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
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>
>>
>> --
>> <>
>>
>> --
>> 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.
Re: [algogeeks] Largest even length palindrome in a string!!
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 wrote:
> Complexity is O(n3) for both above solutions
>
> Ex:
>
> On Sat, Jun 5, 2010 at 3:27 AM, Minotauraus wrote:
>
>> for(int i=0; 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> 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 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
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> <>
>
> --
> 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
--
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.
Re: [algogeeks] Largest even length palindrome in a string!!
1. first find two consecutive letters which are same. 2 point ptr1 to left character and ptr2 to right one 3. now increment ptr2 and decrement ptr1. compare if they are pointing to same characters. if yes repeat this step 4. if no then store in length ptr2-ptr1-2 5. go to step 1 untill all consecutive same letters have been scanned. if the new length found is greater then previous one. then discard previous one and store in length new length. 6. return the substring with largest length On 5 June 2010 15:04, Satya 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 > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- 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.
[algogeeks] Largest even length palindrome in a string!!
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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
