POJ. 1159 Palindrome

1.Problem:
http://poj.org/problem?id=1159

2.Idea:
Using short for less memory usage, and get the longest common substring of reverse string and itself.

3. Source:

 const int MAX_N = 5001;  
 short L[MAX_N][MAX_N];  
 int lcs(string x, string y)  
 {  
      int m = x.length();  
      int n = y.length();  
      int i, j;  
      for (i = 0; i <= m; i++)  
           for (int j = 0; j <= n; j++) {  
                if (i == 0 || j == 0) L[i][j] = 0;  
                else if (x[i - 1] == y[j - 1]) L[i][j] = L[i - 1][j - 1] + 1;  
                else L[i][j] = max(L[i - 1][j], L[i][j - 1]);  
           }  
      return L[m][n];  
 }  
 string s, rs;  
 int n;  
 int main()  
 {  
      cin >> n >> s;  
      rs = s;  
      reverse(s.begin(), s.end());  
      int k = lcs(s, rs);  
      cout << n - k << endl;  
      return 0;  
 }