Posted on 2010-10-13 11:00
李东亮 阅读(1623)
评论(0) 编辑 收藏 引用
ZOJ 2744 Palindromes
这道题要求出一个长度不大于5000的字符串所有子串中回文字符串的个数。可以用暴力brute-force方法解决,但是会TLE。上网搜索了一下大家的解决方案,主要有两种:DP法和分治法。仔细消化了一下,感觉受益匪浅。
首先说下DP方法,其实碰到这种具有很多重复计算的子问题的问题,很容易想到动态规划DP。对于这个问题可以这样理解:每次都从下标0开始搜索长度依次为2、3、……、n的子串,长度为1的子串肯定是回文。所以可以设立数组bool dp[n][n],其中dp[i][i]=true,dp[i][j]表示字符串中从i到j的子串是否是回文,这样对于上面的搜索过程,要判断str[i-j]要是否回文,可以分为两种情况:
1. i和j之间没有其它字符,所以只要str[i]==str[j]即可。
2. i和j之间还有其它的字符,则要求str[i]==str[j]并且dp[i+1][j-1]=true。这也很好理解,从i+1到j-1的子串是回文,再两端加上相同的字符,肯定也是回文。
参考代码如下:
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
using namespace std;
char s[5001];
bool dp[5001][5001];
int main(void)
{
int i, j;
int len;
int cnt;
int k;
while(gets(s))
{
len = strlen(s);
cnt = len;
for (i = 0; i < len; ++i)
{
dp[i][i] = 0;
}
for (i = 1; i < len; ++i)
{
for (j = 0; j < len-i; ++j)
{
k = i+j;
dp[j][k] = false;
if (s[j] == s[k])
{
if (j+1 < k-1)
{
if (dp[j+1][k-1])
{
dp[j][k] = true;
++cnt;
}
}
else
{
dp[j][k] = true;
++cnt;
}
}
}
}
printf("%d\n", cnt);
}
return 0;
}
第二种思路是分治法,对于每个字符可以以它为中心向两端扩展,依次判断,这样同样避免了很多重复判断。在扩展过程中,如果扩展到当前情况发现不是回文,这可以停止扩展。
扩展时需要分两种情况:
1.奇数子串扩展。例如对于字符串ababa,从a[2]=a开始扩展,奇数扩展会考虑a两边的b,是回文,继续向外扩展。
2.偶数子串扩展。对于同样的字符串,从a[2]=a开始扩展 ,都属扩展会依次考虑子串a[1-2]=ba不是回文,停止扩展。
参考代码如下:
#include<stdio.h>
#include<string.h>
int count=0;
char s[5001];
int main(){
int k,l,r;
int len;
while(gets(s)){
count=0;
len=strlen(s);
for(k=1;k<len-1;k++){
l=k-1,r=k+1;
while(l>=0&&r<len){ //奇数长度串
if(s[l--]==s[r++])
count++;
else
break;
}
l=k-1,r=k;
while(l>=0&&r<len){ //偶数长度串
if(s[l--]==s[r++])
count++;
else
break;
}
}
if(s[len-1]==s[len-2]) //偶数长度的串少算了最后两个字符,补上
count++;
count+=len;
printf("%d\n",count);
}
return 0;
}