超级码力在线编程大赛初赛第1场-4-对称前后缀题解

àì夳堔傛蜴生んèń 2022-12-02 12:21 124阅读 0赞

### 目录 ###

*   *  题目描述
     *  示例
     *   *  输入
         *  输出
     *  说明
     *  题解
     *  代码

![在这里插入图片描述][20200830193813780.png_pic_center]

## 题目描述 ##

给定一个字符串s。 我们令一个字符串的权值为一个字符串的最长对称前后缀长度。 **请求出s的所有子串的权值的总和**。 例如，“abcxyzcba” 的最长对称前后缀的长度为3，因为 “abc” 和 “cba” 对称。

字符串的长度为n，1<=n<=3\*1e3。 字符串均由小写英文字符组成。

## 示例 ##

### 输入 ###

“bacbdab”

### 输出 ###

## 说明 ##

样例中，单个字符的子串的权值为1，它们的和为7。 另外的权值为： “bacb” -> 1，“bacbdab” -> 2，“bdab” -> 1，“acbda” -> 1，所以权值和为12。

## 题解 ##

虽然题目中没有明确限制运行时间，但时间复杂度太高会超时。如果用暴力法，首先以O(N2)得到每个子串，之后以O(N)求每个子串的权值，也就是最大对称长度。这样时间复杂度达到了O(N3)。

可以使用动态规划进行优化。我们发现，每个子串的权值可以由它本身的字串的权值求出，因此我们令dp\[i\]\[j\]为下标为i到下标为j构成的字串的权值。状态转移方程为：

> dp\[i\]\[j\]=1, i=j  
> dp\[i\]\[j\]=2, i+1=j && s\[i\]=s\[j\]  
> dp\[i\]\[j\]=dp\[i+1\]\[j-1\]+1, s\[i\]=s\[j\] && i+1<j  
> dp\[i\]\[j\]=0, else

分别对应四种情况：

> 单个字符，如a  
> 两个相同字符，如aa  
> 三个及以上字符，首尾相同，如abca

注意到一个特殊情况：对于形如aba的字串，它的权值应该为3，但按照我们的状态转移方程，dp(“aba”)=dp(“b”)+1=2。

这种情况可以概括为：字串长度等于其权值，则dp\[i\]\[j\]=dp\[i+1\]\[j-1\]+2。这种情况特殊处理就好。

具体过程中，因为每一个问题取决于规模更小（i与j更为接近）的子问题，因此先处理小问题，再处理大问题。所以我选择使用for循环，从小到大遍历i与j的距离d。代码如下：

## 代码 ##

class Solution { 
    	public:
    		long long suffixQuery(string &s) { 
    			int len=s.length();
    			long long dp[len][len];
    			long long sum=0;
    			for(int i=0; i<len; i++) { 
    				dp[i][i]=1;
    				sum++;
    			}
    			for(int d=1; d<len; d++) { 
    				for(int i=0; i<len&&i+d<len; i++) { 
    					//现在求dp[i][i+d]
    					if(d==1) { 
    						if(s[i]==s[i+d]) { 
    							sum+=2;
    							dp[i][i+d]=2;
    						} else { 
    							dp[i][i+d]=0;
    						}
    					} else { 
    						if(s[i]==s[i+d]) { 
    							if(dp[i+1][i+d-1]==d-1) { 
    								dp[i][i+d]=2+dp[i+1][i+d-1];
    								sum+=dp[i][i+d];
    							} else { 
    								dp[i][i+d]=1+dp[i+1][i+d-1];
    								sum+=dp[i][i+d];
    							}
    
    						} else { 
    							dp[i][i+d]=0;
    						}
    					}
    				}
    			}
    			return sum;
    		}
    
    };

[20200830193813780.png_pic_center]: /images/20221123/1e440aa9dccc4aff83935c3a54303f9e.png