最长回文子串

发表于   |   分类于   |  

暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;

string findMaxPa(char* str)
{
	int len=strlen(str);
	int MAX=1;
	int left=0;
	int right=0;
	string s="";
	for(int i=0;i<len;i++)//起始地址
	{
		for(int j=i+1;j<len;j++)//结束地址
		{
		    int temp1,temp2;
			for(temp1=i,temp2=j;temp1<temp2;temp1++,temp2--)//判断是否是回文
			{
				if(str[temp1]!=str[temp2])
					break;
			}
			if(temp1>=temp2)//如果是回文
			{
				int cut=j-i+1;
				if(cut>MAX)
				{
				    MAX=cut;
					left=i;
					right=j;
				}
			}
		}
	}
	for(int i=left;i<=right;i++)
	{
		s+=str[i];
	}
	return s; 
}

int main()
{
	char str[100];
	while(scanf("%s",str)!=EOF)
	{
		string s=findMaxPa(str);
		cout<<s<<endl;
	}
	return 0;
}

时间复杂度为O(n^3)

动态规划

初始状态：

  • dp[i][i]=true
  • dp[i][i+1]=true if(str[i]==str[i+1])

转换方程：

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
string findMaxPa(char* str)
{
	bool dp[50][50]={false};
	int len=strlen(str);
	//一开始设定第一个字符为回文，长度为1
	int start=0; 
	int MAX=1;	
	//初始化
	for(int i=0;i<len-1;i++)
	{
		dp[i][i]=true;
		if(str[i]==str[i+1])
		{
			dp[i][i+1]=true;
			start=i;
			MAX=2;
		}
	}
	dp[len-1][len-1]=true;
	//主体
	for(int L=3;L<=len;L++)//子串长度
	{
		for(int i=0;i<=len-L;i++)//子串起始地址
		{
			int j=i+L-1;//结束地址
			if(dp[i+1][j-1]&&str[i]==str[j])
			{
				MAX=L;
				start=i;
				dp[i][j]=true;
			}
		}
	}
	string s="";
	for(int i=start;i<MAX+start;i++)
	{
		s+=str[i];
	}
	return s;
}
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(n^2)