南阳oj37回文字符串

[c++]代码库

/*
将字符串逆序，找出原字符串与该字符串的公共子序列，则其余部分为需要添加的字符
状态转移方程参考最长公共子字符串
http://www.cnblogs.com/qq188380780/p/6678471.html
*/
#include<cstdio>
#include<cstring>
#define Max(a,b) ((a)>(b)?(a):(b))
char a[1005],b[1005];
int d[1005][1005];

void solven(int len)
{
    int i,j;
    for(i=1; i<=len; ++i)
    {
        for(j=1; j<=len; ++j)
        {
            if(a[i-1] == b[j-1])
                d[i][j] = d[i-1][j-1] + 1;
            else
                d[i][j] = Max(d[i-1][j],d[i][j-1]);
        }
    }
}

int main()
{
    int t,i,j,len;
    scanf("%d",&t);
    while(t--)
    {
        memset(d,0,sizeof d);
        scanf("%s",a);
        len = strlen(a);
        for(i=0; i<len; ++i)
            b[i] = a[len-1-i];
        solven(len);
        printf("%d\n",len-d[len][len]);
    }
    return 0;
}

//空间优化，与最长公共子序列一样
#include<cstdio>
#include<cstring>

char a[1005],b[1005];
int d[1005];

void solven(int len)
{
    int i,j,t,temp;
    for(i=0; i<len; ++i)
    {
        for(j=t=0; j<len; ++j)
        {
            temp = d[j];
            if(a[i] == b[j])
                d[j] = t + 1;
            else if(d[j] < d[j-1])
                d[j] = d[j-1];
            t = temp;
        }
    }
}

int main()
{
    int t,i,j,len;
    scanf("%d",&t);
    while(t--)
    {
        memset(d,0,sizeof d);
        scanf("%s",a);
        len = strlen(a);
        for(i=0; i<len; ++i)
            b[i] = a[len-1-i];
        solven(len);
        printf("%d\n",len-d[len-1]);
    }
    return 0;
}

//另可不必再开数组存逆序，只需要记录位置即可
#include<cstdio>
#include<cstring>

char a[1005];
int d[1005];

void solven(int len)
{
    int i,j,t,temp;
    for(i=0; i<len; ++i)
    {
        for(j=t=0; j<len; ++j)
        {
            temp = d[j];
            if(a[i] == a[len-1-j])
                d[j] = t + 1;
            else if(d[j] < d[j-1])
                d[j] = d[j-1];
            t = temp;
        }
    }
}

int main()
{
    int t,i,j,len;
    scanf("%d",&t);
    while(t--)
    {
        memset(d,0,sizeof d);
        scanf("%s",a);
        len = strlen(a);
        for(i=0; i<len; ++i)
            b[i] = a[len-1-i];
        solven(len);
        printf("%d\n",len-d[len-1]);
    }
    return 0;
}