回文字符串

（1）判断一个字符串是不是回文子串,分为两种情况，一种是字符串的长度为奇数个，另一种为偶数个，当为偶数个时对称相等就行。当为奇数个时，注意考虑要有一个字符的情况。

代码实现：

#include<iostream>
#include<string.h>
using namespace std;
int main()
{ int n;
  cin>>n;
  while(n--)
  { string s;
     cin>>s;
     int m=s.size();
     int a=0;
     if(!(m%2))
     { for(int i=0,j=m-1;i<j;i++,j--)
        if(s[i]==s[j]) a+=2;
        if(a==m) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
     }
     else
     { if(a==1) cout<<"YES"<<endl;
       else{
            for(int i=0,j=m-1;i<j;i++,j--)
              if(s[i]==s[j]) a+=2;
              if(a==m-1)  cout<<"YES"<<endl;
              else  cout<<"NO"<<endl;
            }
     }
  }
  return 0;
}

（2）给你一个字符串求最少需要添加几个字符使其成为回文字符串，这个题可以转化为求最长公共子序列的长度。。然后A[length]-dp[A[length]][A[length]];

#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
using namespace std;
int dp[1001][1001] ;
int main()
{ int n;
  cin>>n;
  while(n--)
  {   string s,s1;
      cin>>s;
      for(int i=s.size()-1;i>=0;--i)
        s1+=s[i];
        memset(dp,0,sizeof(dp));
        int m=s.size();
        for(int i=0;i<m;i++)
          for(int j=0;j<m;++j)
            if(s[i]==s1[j]) dp[i+1][j+1]=dp[i][j]+1;
            else  dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
             cout<<m-dp[m][m]<<endl;
  } return 0;
}

法二：

 
#include<iostream>
#include<string>
#include<algorithm>
#include<string.h>
using namespace std;
const int N=1001;
int a[N],b[N];//开辟一个动态数组
int main()
{ //freopen("1.txt","r",stdin);
	int n;
  cin>>n;
  while(n--)
  {   memset(a,0,sizeof(a));
      memset(b,0,sizeof(b));
	  string s,s1;
     cin>>s;
	 s1=s;
	 reverse(s1.begin(),s1.end());
	 for(int i=0;i<s.size();++i)
		{ for(int j=0;j<s1.size();++j)
			 if(s[i]==s1[j])
				 a[j+1]=b[j]+1;//b[j]相当于dp[i-1][j-1],a[i]相当于dp[i][j]
			 else  a[j+1]=b[j+1]>a[j]?b[j+1]:a[j];//a[j]相当于dp[i][j-1],b[j+1],相当于dp[i-1][j];
			 for(int j=1;j<=s1.size();++j)
				 b[j]=a[j];
	     }
	   cout<<s.size()-b[s.size()]<<endl;
  }return 0;
}        

（3） 给你一个字符串，求这个字符串的最长回文子串并输出。。方法枚举法。。。

#include<stdio.h>
#include<string.h>
#include<ctype.h>
#define N 5001
char buf[N],s[N];
int p[N]; //存储字母的初始位置 
int main()
{  int Case;
  scanf("%d",&Case);
  getchar();
  while(Case--)
  {      //gets(buf);
       fgets(buf,sizeof(s),stdin);
       int n=strlen(buf);
       int m=0,max=0,x,y,i,j,k;
        for(int i=0;i<n;++i)
          if(isalpha(buf[i]))//判断字符是否为字母 
           {  p[m]=i;
             s[m++]=toupper(buf[i]);//将大写字母转化为小写字母 
           }
          for( i=0;i<m;++i)
           { for( j=0;i-j>=0&&i+j<m;++j)//枚举字字符串长度为奇数时 
              {
              if(s[i-j]!=s[i+j]) break;
               if(max<2*j+1)
                { max=2*j+1;
                 x=p[i-j];
                 y=p[i+j];
                }
              }
              for( j=0;i-j>=0&&i+j+1<m;++j)//枚举字符串长度为偶数时 
                {
                  if(s[i-j]!=s[i+j+1]) break;
                  if(2*j+2>max)
                  { max=2*j+2;
                   x=p[i-j];
                   y=p[i+j+1];
                   }
                }
           }
           for(k=x;k<=y;++k)
           printf("%c",buf[k]);
           printf("\n");
           
  }  return 0;
}