UVa 11151 - Longest Palindrome

题目：求最常回文子串。

分析：dp、LCS，求一个串的最常回文子串就是本串与翻转串之间的最大公共子序列。

注意：数据中有空串。

[cpp] 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
 
char string[ 1005 ]; 
char revstr[ 1005 ]; 
int  f[ 1005 ][ 1005 ]; 
 
int main() 
{ 
    int T;  
    while ( scanf("%d",&T) != EOF ) { 
        getchar(); 
        for ( int t = 1 ; t <= T ; ++ t ) { 
            gets(string); 
            int len = strlen(string); 
            for ( int i = 0 ; i < len ; ++ i )   
                revstr[len-i-1] = string[i]; 
             
            memset( f, 0, sizeof(f) ); 
            for ( int i = 1 ; i <= len ; ++ i ) 
            for ( int j = 1 ; j <= len ; ++ j ) 
                if ( string[i-1] == revstr[j-1] ) 
                    f[i][j] = f[i-1][j-1]+1; 
                else { 
                    f[i][j] = f[i-1][j]; 
                    if ( f[i][j] < f[i][j-1] ) 
                        f[i][j] = f[i][j-1]; 
                } 
            printf("%d\n",f[len][len]); 
        } 
    } 
    return 0; 
} 

补充：软件开发 , C++ ,

上一个：递归法求两数最大公约数
下一个：UVa 443 - Humble Numbers