Posted on 2010-10-13 11:00
李東亮 閱讀(1643)
評論(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;
}