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 <[email protected]> wrote: > Complexity is O(n3) for both above solutions > > Ex: aaaaaaaa > > On Sat, Jun 5, 2010 at 3:27 AM, Minotauraus <[email protected]> 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 <[email protected]> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
