red_coder's blog

SPOJ STUCK :(
By red_coder, 11 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

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

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

→ Reply
»
11 years ago, # |
  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
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Question is how to do that...

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Observe that L(i,j) is only dependent on L(i-1, j') and L(i,j') ==> you can reuse the memory of L in previous rows.

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

Someone pls help.....

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

finally got accepted :)

→ Reply