超级码力在线编程大赛初赛第1场-4-对称前后缀题解
目录
- 题目描述
- 示例
- 输入
- 输出
- 说明
- 题解
- 代码
题目描述
给定一个字符串s。 我们令一个字符串的权值为一个字符串的最长对称前后缀长度。 请求出s的所有子串的权值的总和。 例如，“abcxyzcba” 的最长对称前后缀的长度为3，因为 “abc” 和 “cba” 对称。
字符串的长度为n，1<=n<=3*1e3。 字符串均由小写英文字符组成。
示例
输入
“bacbdab”
输出
12
说明
样例中，单个字符的子串的权值为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;
}
};