回文字符序列-白红宇

回文字符序列

阅读量：4709 次

发布时间：2019-06-10

本文共 1683 字，大约阅读时间需要 5 分钟。

转载

1、问题描述

描述

给定字符串，求它的回文子序列个数。回文子序列反转字符顺序后仍然与原序列相同。例如字符串aba中，回文子序列为"a", "a", "aa", "b", "aba"，共5个。内容相同位置不同的子序列算不同的子序列。

输入

第一行一个整数T，表示数据组数。之后是T组数据，每组数据为一行字符串。

输出

对于每组数据输出一行，格式为"Case #X: Y"，X代表数据编号（从1开始），Y为答案。答案对100007取模。

数据范围

1 ≤ T ≤ 30

小数据

字符串长度 ≤ 25

大数据

字符串长度 ≤ 1000

样例输入

5abaabcbaddabcba12111112351121cccccccfdadfa

样例输出

Case #1: 5Case #2: 277Case #3: 1333Case #4: 127Case #5: 17

2、分析

定义dp(i,j)表示串[i,j]之间的回文子串的个数，那么可以得到如下递推式：

dp(i,j)=dp(i+1,j)+dp(i,j-1)+res (j-i>0)其中res要分情况讨论：

(1)如果s[i]==s[j]那么中间重叠部分dp(i+1,j-1)不需要减去，只需要再加上一个空串的情况即可，即res=1；

反之，根据容斥原理，需要减去中间重叠计算的部分，即res=-dp(i+1,j-1)。

当i==j时，即只有一个字符，那就是1,这样便不难通过递推式求出最终的答案了，最终的答案是dp(1,len+1)。len表示输入的串的长度，起点从1开始。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
             9 #include
             
              10 #include
              
               11 #include
               
                12 #include
                
                 13 #include
                 
                  14 #include
                  
                   15 #include
                   
                    16 #include
                    
                     17 using namespace std;18 19 #define mod 10000720 int dp[1005][1005];21 char s[1005];22 23 int F(int l, int r) 24 {25 if (dp[l][r] != -1) 26 return dp[l][r];27 if (l > r) 28 return dp[l][r] = 0;29 if (l == r) 30 return dp[l][r] = 1;31 int& ret = dp[l][r];32 33 ret = (F(l + 1, r) + F(l, r - 1)) % mod;34 35 if (s[l] == s[r]) 36 ++ret;//首尾相等时，多加上一个中间为空的情况37 else 38 ret -= F(l + 1, r - 1);//否则，减去重叠部分39 40 ret = (ret + mod) % mod;41 return ret;42 }43 44 int main()45 {46 47 int cas = 0, t;48 cin >> t;49 while (t--) 50 {51 memset(dp, -1, sizeof(dp));52 cin >> (s+1);53 int ans = F(1, strlen(s + 1));54 printf("Case #%d: %d\n", ++cas, ans);55 }56 return 0;57 }

转载于:https://www.cnblogs.com/LCCRNblog/p/4448803.html

你可能感兴趣的文章

编写一个程序，将d:\java目录下的所有.java文件复制到d:\jad目录下，并将原来文件的扩展名从.java改为.jad。...