@all:
T(i,j) : denotes the length of longest palindrome with start index
i and end index j index.
T(i,j )=
max {
1 , if i == j;
2+T(i+1,j-1) if x[i] == x[j];
max(T(i+1,j) T(i,j-1))
}
This is the recurrence relation
Now algorithm:
T(i,i-1) = 0 for 1<= i <= n.
for i= 1 to n
T(i)(i) = 1;
start with the distnace d
for d = 1 to n
for i = 1 to n -d
{ j = i+d;
if(x[i] == x[j])
T[i][j] = 2+ T[i+1][j-1];
else
T[i][j] = max (T[i+1][j], T[i][j-1])
}
return T[1][n];
On Tue, Sep 1, 2009 at 12:01 AM, Dufus<[email protected]> wrote:
>
> This is one of the most difficult dynamic programming problem I have
> faced so far.
>
> A good discussion on this problem and different solutions can be found
> at
> http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/
>
> _dufus
>
>
> On Aug 31, 6:01 pm, ankur aggarwal <[email protected]> wrote:
>> @abhijeet
>> dryrun on this
>>
>> abbaabba
>>
>> On Mon, Aug 31, 2009 at 5:45 PM, Abhijeet Kumar
>> <[email protected]>wrote:
>>
>> > u can push the string onto a stack ... so last element will be on top ...
>> > den u can pop out element and compare ...
>> > if u have 2 or more set of palindromes ..
>> > u can keep a counter and keep a check on dat...
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
