red_coder's blog

SPOJ STUCK :(
By red_coder, 13 years ago, In English

hey guys here is a simple DP Problem, to solve it i found the LCS of original and reversed string and then substracted this length from the length of given string. I am getting TLE. I used a bottom-up approach.My code is given below.Can anyone help me out??


char A[5005];
int L[5005][5005];
int n;

int ch()  //this function calculates the LCS of original string and reversed string
{

    f(i,0,n)
    {
        f(j,0,n)
        {
            if(A[i]==A[n-1-j])
            {
                L[i][j]=1;
                if(i!=0 && j!=0)
                L[i][j]+=L[i-1][j-1];
            }
            else
            {
                int x=0,y=0;
                if(i>0) x=L[i-1][j];
                if(j>0) y=L[i][j-1];
                L[i][j]=max(x,y);
            }
        }
    }
    return L[n-1][n-1];
}



int main()
{

    si(n);
    scanf("%s",A);
    //puts(B);
    printf("%d\n",n-ch());
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
13 years ago, hide # |
← Rev. 3  
Vote: I like it -6 Vote: I do not like it

I think it is a Levenshtein distance problem..[link]

→ Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

You should try to reduce the size of L. It does help a lot.

→ Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Someone pls help.....

→ Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

finally got accepted :)

→ Reply