回文字符串
Longest Palindromic Substring:最长回文子串
最长回文子串问题。
Manacher 解法的核心点在于：(1)使用特殊字符填充原字符串，使其变成奇数长度的字符串，并且使得最长回文子串的长度等于 P -1。(2)在对每一位 i 求取以该位为轴心的最长回文子串时候，利用了对称原理减少了部分的重复匹配，从而使得其与中心扩展法相比具有一定的性能优化。
Longest Palindromic Subsequence:最长回文子序列
回文序列(Palindromic sequence, Palindrome)是指正向遍历和反向遍历完全相同的序列，例如字符串“AAAAA”显然是一个回文序列，又如字符串“ABC@CBA”也是一个回文序列。现在，我们要在一个(字符)序列中找出最长回文子序列的长 度。例如字符序列"BBABCBCAB"，最长回文子序列是“BACBCAB”(可能不唯一)，它的长度是 7；子序列"BBBBB"和"BBABB"虽然 也是回文序列，但却不是最长的，因此不合题意。
- 方法 1：设 Sp 是序列 S 的最长回文子序列，又设 ST 是 S 的转置(逆序)，则 Length(Sp)=LCS(S, ST)，即LPS(S)=LCS(S, ST)。
- 方法 2：
又可以喜大普奔填表格了，以"BBABCBCAB"为例：
空间复杂度优化：选取表中的两列，自下而上，自左向右滚动更新。
一个例子：poj1159 Palindrome
求出题中所给出序列的 LPS，再用序列长度-LPS，即为需要添加的字符数目。时间复杂度 O(n^2)，空间复杂度 O(n)。
#include <stdio.h>
#include <string.h>
#define MAXN 5010
int AnsTab[2][MAXN]; //对应表格的最左边两列，自下而上，自左向右，滚动刷新
char inSeq[MAXN];
int mymax(int a, int b)
{
return (a>b)?a:b;
}
int FindLenLPS(int n)
{
//Init
for (int i=0; i<2; ++i)
{
for (int j=0; j<n; ++j)
{
AnsTab[i][j]=0;
}
}
AnsTab[0][0]=1;
int refresh_col; //这次该刷新AnsTab的哪一列？
int base_col; //根据base_col刷新refresh_col
for (int i=1; i<n; ++i) //从第一列开始，共需更新n-1列(次);自左向右
{
refresh_col=i%2;
base_col=1-refresh_col;
AnsTab[refresh_col][i]=1;
for (int j=i-1; j>=0; --j) //自下而上
{
//应用状态转移方程
if (inSeq[j]==inSeq[i])
{
AnsTab[refresh_col][j]=2+AnsTab[base_col][j+1];
}
else
{
AnsTab[refresh_col][j]=mymax(AnsTab[refresh_col][j+1], AnsTab[base_col][j]);
}
}
}
return AnsTab[(n-1)%2][0]; //这就是LPS的长度
}
int main()
{
int n;
scanf("%d", &n);
scanf("%s", inSeq);
printf("%d\n", n-FindLenLPS(n));
return 0;
}
Cheapest Palindrome:最小代价构造回文字符串
仅考虑字符个数
动态规划解: f(i,j)表示 s[i..j]变为回文串需要添加的最少字符数。f(i,j)=0 if i>=j f(i,j)=f(i+1,j-1) if i<j and s[i]==s[j] f(i,j)=min(f(i,j-1),f(i+1,j))+1 if i<j and s[i]!=s[j]
#include <iostream>
#include <string.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
int f[100][100];
int main()
{
string s;
while (cin>>s)
{
memset(f,0,sizeof(f));
for (int i=s.length()-1;i>=0;i--)
for (int j=i+1;j<s.length();j++)
if (s[i]==s[j])
f[i][j]=f[i+1][j-1];
else
f[i][j]=min(f[i][j-1],f[i+1][j])+1;
cout<<f[0][s.length()-1]<<endl;
}
return 0;
}
字符含有添加/删除权重
这里经典的题目是POJ 3280
题目大意是说一个字符串，每插入或者删除一个字符都需要一定的代价，问怎样可以使这个字符串变成一个回文串，且花费最小。首先明确的就是如果已经将区间[i,j]整理成为一个回文串(不管中间有多少个字 符或者是以什么字符开头或者结尾)，当 DP 到区间[i,j+1]时，我们可以在 i-1 的位置添加一个 str[j+1]字符，或者将在 j+1 处的字符删除，得到一个新的回文串，而且我们这两步操作都没有借助或者影响区间[i,j]的情况。因此，那我们就可以将添加或者删除整合在一起，对字符 str[j+1]的操作就按照添加和删除中花费最小的一个计算。写出状态转移方程: DP[j][i] = MIN(DP[j+1][i]+cost[str[j]-‘a’], DP[j][i-1]+cost[str[i]-‘a’]); if(str[i] == str[j])DP[j][i] = MIN(DP[j][i],DP[j+1][i-1]); 这里的 j 是按照 i-1 到 0 枚举的，由于可能 str[i] == str[j]，因此也可以不操作，再将 不操作 与 添加或删除区间头或尾 比较。当然，其实最初的想法是扩展出来四个状态，就是首删除，首添加，尾删除，尾添加，由此扩展开来求一个最小值
#include <stdio.h>
#include <string.h>
#define mem(a) memset(a,0,sizeof(a))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
int DP[2005][2005],cost[30],N,M;
char str[2005];
int main()
{
while(~scanf("%d%d", &M, &N))
{
mem(DP); mem(str); mem(cost);
scanf("%s%*c",str);
char ch; int x, y;
for(int i=0;i<M;i++)
{
scanf("%c %d %d%*c", &ch, &x, &y);
cost[ch-'a'] = MIN(x,y);
}
for(int i=1;i<N;i++)
{
for(int j=i-1;j>=0;j--)
{
DP[j][i] = MIN(DP[j+1][i]+cost[str[j]-'a'], DP[j][i-1]+cost[str[i]-'a']);
if(str[i] == str[j])DP[j][i] = MIN(DP[j][i],DP[j+1][i-1]);
}
}
printf("%d\n", DP[0][N-1]);
}
return 0;
}
Palindrome Partitioning:切分回文子串
全部回文子串
本题可以参考Leetcode Palindrome Partitioning，即在给定字符串的情况下，寻找所有可能切分为回文子串的组合方法。譬如s = "aab"，所有的组合为:
[
["aa","b"],
["a","a","b"]
]
最简单的方法，即是使用回溯法寻找所有可能的子串，然后判断是否为回文子串，代码参考这里:
package wx.ds.string.palindrome;
/**
* Created by apple on 16/9/2.
*/
import org.junit.Assert;
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
/**
* @function 回文子串划分问题
*/
public class PalindromePartition {
/**
* @param str
* @param partitionedStr
* @param result
* @param pos
* @function 使用回溯法进行所有的回文子串切分
*/
public void partitionBacktracking(String str, List<String> partitionedStr, List<List<String>> result, int pos) {
//判断当前字符串是否到头了
if (pos == str.length()) {
//将本次的结果添加到result中
result.add(new ArrayList<String>(partitionedStr));
return;
}
//否则开始递归求取字符串
for (int i = pos + 1; i < str.length() + 1; i++) {
String subStr = str.substring(pos, i);
//判断是否为回文字符串
if (isPal(subStr)) {
partitionedStr.add(subStr);
//递归调用
partitionBacktracking(str, partitionedStr, result, i);
//回溯
partitionedStr.remove(partitionedStr.size() - 1);
} else {
//否则直接跳过
continue;
}
}
}
@Test
public void test_partitionBacktracking() {
List<String> partitionedStr = new ArrayList<>();
List<List<String>> result = new ArrayList<>();
partitionBacktracking("afdafabbacddadscadsfdsaab", partitionedStr, result, 0);
System.out.println(result);
}
/**
* @param s
* @return
* @function 判断字符串s是否为回文字串
*/
private boolean isPal(String s) {
int i = 0;
while (i < s.length() / 2) {
if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
return false;
}
i++;
}
return true;
}
@Test
public void test_isPal() {
Assert.assertEquals(isPal("a"), true);
Assert.assertEquals(isPal("ab"), false);
Assert.assertEquals(isPal("abba"), true);
Assert.assertEquals(isPal("abdba"), true);
Assert.assertEquals(isPal("abdbad"), false);
}
}