最长公共子序列 LCS
也是DP入门题,紫书第九章
这里讲得很清晰:
http://www.cnblogs.com/xudong-bupt/archive/2013/03/15/2959039.html
n^2模板:
int n,m; char a[MAXN],b[MAXN],res[MAXN]; int dp[MAXN][MAXN],dir[MAXN][MAXN]; //dir 1斜上,2左,3上 void lcs(int al,int bl) { int i,j; for(i=1;i<=al;i++) { for(j=1;j<=bl;j++) { if(a[i-1] == b[j-1]) { dp[i][j] = dp[i-1][j-1]+1; dir[i][j] = 1; } else if(dp[i-1][j]>dp[i][j-1]) { dp[i][j] = dp[i-1][j]; dir[i][j] = 3; } else { dp[i][j] = dp[i][j-1]; dir[i][j] = 2; } } } } void getlcs(int al,int bl) { int i = al; int j = bl; int k = 0; while(i && j) { if(dir[i][j] == 1) { res[k++] = a[i-1]; i--;j--; } else if(dir[i][j]==2) j--; else if(dir[i][j]==3) i--; } for(int v = k-1;v>=0;v--) pf("%c",res[v]); }
nlogn复杂度:
这个不是稳定的nlogn,事实上,LCS没有稳定的nlogn算法,只有在一定限制条件下才有可能达到。
这里的限制条件是:
A中元素在B中的序号对数很少
若是aaaa,aaaaaaa的话,则是n*nlogn复杂度,比普通lcs还慢
具体讲解:http://blog.csdn.net/wdq347/article/details/9001005
(1) 对序列B排序
(2) 计算A中每个元素在B中的序号,并构成新序列
(3) 使用LIS的方法计算最长严格递增子序列
(4) 获取最长公共子序列
性能分析:
(1) 排序复杂度为nlogn
(2) 获取一个元素在B中的序号的复杂度,最小为logn,最大为n,获取所有元素的复杂度为 nlogn === n*n
(3) LIS 复杂度为nlogn
因此总体复杂度在nlogn 到 n*n logn之间,但如果(2) 步骤中A中元素在B中的序号对数很少时,性能相当优越,在实际测试时,string 中均为小写字母,长度为10000的情况下,这种方法比普通的LCS快一倍以上;如果string 中的字符扩展成char,即0-255,则这种方法比普通的LCS快至少一个数量级
模板:
char a[MAXN],b[MAXN]; int g[MAXN],s[MAXN]; vector<int> p[26]; int lcs(int al,int bl) { int i,j,z,y=0; for(i=0;i<=26;i++) p[i].clear(); for(i=bl-1;i>=0;--i) p[b[i]-'a'].pb(i); for(i=0;i<al;++i) for(j=0,z=p[a[i]-'a'].size();j<z;++j) s[y++]=p[a[i]-'a'][j]; mem(g,INF); int ans=0; for(i=0;i<y;++i) { int k=lower_bound(g,g+y,s[i])-g; ans = max(ans,k+1); g[k]=s[i]; } return ans; }
连续和不连续:
http://www.cnblogs.com/xubenben/p/3330712.html