PAT-A1040(C/C++代码解析)

1040 Longest Symmetric String (25 分)

法一：暴力法

#include 
#include 
#include 
#include 
using namespace std;  

int pan (int i,int j,char* str)
{
	while (i<=j)
	{
		if (str[i]!=str[j])
		return 1;
		i++;
		j--;
	}
	return 0;
}

int main ()
{
    char str[1010];
    cin.getline (str,1010);
    int i,j,MAX=-1;
	for (i=0;iMAX)
				MAX=j-i+1;
			}
		}
	}
	printf ("%d",MAX);
    return 0;
}

法二：动态规划

#include 
#include 
#include 
using namespace std;
int main ()
{
    char str[1010];
    cin.getline (str,1010);
    int L=3,i,j,dp[1010][1010],ans=1,l=strlen(str);
	memset (dp,0,sizeof (dp));
	for (i=0;i 
法三：Manacher算法
 
#include
#include
#include
using namespace std;
const int maxn=11000005;
char st[maxn];//原字符串
char tmp[maxn<<1];//转换后的字符串
int Len[maxn<<1];//Len[i]表示以字符tmp[i]为中心的最长回文字串的最右字符到tmp[i]的长度
int INIT(char *st)
{
    int i,len=strlen(st);
    tmp[0]='@';//字符串开头增加一个特殊字符，防止越界
    for(i=1;i<=2*len;i+=2)
    {
        tmp[i]='#';
        tmp[i+1]=st[i/2];
    }
    tmp[2*len+1]='#';
    tmp[2*len+2]='$';//字符串结尾加一个字符，防止越界(首尾两字符不可相同)
    tmp[2*len+3]=0;
    return 2*len+1;//返回转换字符串的长度
}
//Manacher算法计算过程
int MANACHER(char *st,int len)
{
     int maxx=0,ans=0,po=0;//设maxx为之前计算中最长回文子串的右端点的最大值，并且设取得这个最大值的位置为po
     for(int i=1;i<=len;i++){
         if(maxx>i){
         	Len[i]=Len[maxx-i];//对称性可知：len[i] 和 len[j]
     	 }
         else{
         	Len[i]=1;//如果i>=mx，要从头开始匹配
		 }
         while(tmp[i-Len[i]]==tmp[i+Len[i]]){//老老实实地匹配
         	Len[i]++;
     	 }
         if(Len[i]+i>maxx)//若新计算的回文串右端点位置大于mx，要更新po和mx的值
         {
             maxx=Len[i]+i;
             po=i;
         }
         ans=max(ans,Len[i]);
     }
     return ans-1;//返回Len[i]中的最大值-1即为原串的最长回文子串的长度
}
int main(){
	cin.getline(st,11000005);
	int len = INIT(st);
	printf("%dn",MANACHER(st,len));
	return 0;
}