Posted on 2010-10-13 11:00
李东亮 阅读(1621)
评论(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;
}