最长公共子序列 ★★★★★★

[MiaoMiao]

题目描述：
给定一个序列a,b,c,d,e,f,g，
其子序列的定义就是在当中任意删掉若干个元素，
例如a,b,e,g就是其中一个子序列。
现给定两个字符串，要求出它们的最长公共子序列的长度

输入：
多组测试数据，每两个字符串组成一组，
中间用空格或者换行符分隔
单个字符串最大长度为200000字节，或者100000个全角(或混合)字符。
以EOF标志结束输入。

输出：
对于每组测试数据，输出一行，每行仅输出一个数，
表示它们的最长公共子序列的长度

样例输入：
大家好 才是真的好
abcdefg acegbdf
天气真是好 这个天气就是好
Congratulations 恭喜你

样例输出：
1
4
4
0

其它信息：
连续两个ascii>127的字符应当视为全角字符对待，要看成一个整体。
但如果相邻两个一个>127，但另一个在127以内，那么这两个
不应该作为全角字符看待。

[MiaoMiao]

#include <stdio.h>
#include <string.h>
#define L 256*1024
int
lcsl(const char * s1,int s1l,const char * s2,int s2l)
{
int i,j,xl,yl,yy=0,c[2][L];
const char *x,*y;
s1l<s2l?((x=s1),(xl=s1l),(y=s2),(yl=s2l)):((y=s1),(yl=s1l),(x=s2),
(xl=s2l));
for(i=0;i<yl;++i)c[0][i]=c[1][i]=0;
for(i=1;i<=xl;++i){
if(yy&&i>=2&&0>x[i-1]&&0>x[i-2]){
for(j=1;j<=yl;++j){
((3+i)%2)?(c[0][j]=c[1][j]):(c[1][j]=c[0][j]);
}
yy=0;
}else if((2+i)%2){
for(j=1;j<=yl;++j){
if(x[i-1]==y[j-1]){
c[1][j]=c[0][j-1]+1;
if((0>x[i-1])&&(0>x[i])&&(x[i]==y[j])){
c[1][j+1]=c[0][j-1]+1;
yy=1;++j;
}
}else{
c[1][j]=(c[0][j]>=c[1][j-1])?c[0][j]:c[1][j-1];
}
}
}else{
for(j=1;j<=yl;++j){
if(x[i-1]==y[j-1]){
c[0][j]=c[1][j-1]+1;
if((0>x[i-1])&&(0>x[i])&&(x[i]==y[j])){
c[0][j+1]=c[1][j-1]+1;
yy=1;++j;
}
}else{
c[0][j]=(c[1][j]>=c[0][j-1])?c[1][j]:c[0][j-1];
}
}
}
}
return c[(2+xl)%2][yl];
}
int
main(void)
{
char x[L],y[L];
while(EOF!=(fscanf(stdin,"%s%s",x,y))){
fprintf(stdout,"%d\n",lcsl(x,strlen(x),y,strlen(y)));
}
return 0;
}

[TCPIPer]

程序应该还有点问题丫：（

[MiaoMiao]

转贴的:::::::::::::::::::::::::::::::::::::::::::

超稀疏LCS快速解法(因这里帖子字数限制，暂不提供源代码)
相关题目http://yzfy.org/bbs/viewthread.php?tid=611

问题：两组由一个有限字符集（Unicode）组成的字符串，
求最长公共子序列（LCS）的长度，其中字符串中的字符为随机生成。

要解决这个问题，我们首先回顾LCS的经典DP解法，
假如给你A="abacbc"和B="bcacabc"
记dp(a,b)的值为串A前a个字符和串B前b个字符的最长公共子序列的长度，
那么其状态转移方程为：
dp(a,b) = dp(a-1,b-1)+1; (A[a]==B[b])
= max(dp(a-1,b), dp(a,b-1)); (A[a]!=B[b])
应用状态转移方程列表求解：
_abacbc
_0000000
b0011111
c0011222
a0112222
c0112333
a0112333
b0122344
c0122345 (列表1)
（列表中第i行j列(i,j)的数值的生成：
当左边第i个字符和上面第j个字符一样的时候，取(i-1,j-1)的数值加1作为(i,j)的结果，
否则取(i-1,j)和(i,j-1)中的较大者）
最右下方的数字是5，所以最长公共子序列的长度就是5（对应一解为"bacbc"）
其时间复杂度为O(len(A)*len(B))

根据状态转移方程，我们可以得到：
dp(a-1,b)<=dp(a,b)
dp(a,b-1)<=dp(a,b)
|dp(a-1,b-1)-dp(a,b)| <= 1
也就是说相邻元素之间的差绝不会超过1。
那么，之前的列表我们完全可以改写为如下形式而没有歧义：
_abacbc
_0000000
b0010000
c0010100
a0101000
c0101100
a0101100
b0110110
c0110111 (列表2)
最下面一行的1的总个数就是答案。
也就是说上面这个列表从左到右看，只记录哪个位置需要进行加1
如果您已经明白这个，那再接着，这个列表再改写为：
abacbc
b 1
c 1,3
a 0,2
c 0,2,3
a 0,2,3
b 0,1,3,4
c 0,1,3,4,5 (列表3)
现在这个列表只记录1出现的位置，例如第四行c 0,2,3表示那一行的1，
出现在第0,2,3三个位置（必须从小到大）
那么最后一行有多少个数，答案就是多少。
从这个第三个表还可以观察出如下规律：上方的数不小于它下面的数，
下一行至多比上一行多出一个数。

变成这个形式后，怎么从上一行递推到下一行呢？现在用
a 0,2,3
b 0,1,3,4
这两行作为例子，第二行的b与原字符串有相同字符的地方是1,4，表示为：
#b 1,4 (注意加了个'#'以示区别)
然后和上一行放在一起比较：
a 0,2,3
#b 1,4
第一个1在上一行的(0,2]之间（左开右闭），
就把它所对应的区间的大的那一端的数，改为当前数，
即变成0,1,3
轮到第二个数4，如果那个数比上一行任意一个数都要大，
就把它直接加在最后，得到b 0,1,3,4就是下一行了。

但要注意，如果下一行不止一个数属于上一行的同一个区间的话，如：
a 0,2,3
#b 1,2,4,5 (b与原串相同字符的位置分别为1,2,4,5)
推导出的下一行仍然为b 0,1,3,4
也即#b中属于上一行相同区间的最小一个数才计算，以后的就直接丢弃。

为了使此算法进行字符配对更快，我们需要对字符串A进行类似KMP的预处理。
这样最终的时间复杂度将与列表4中的1的总个数密切相关：
abacbc
b010010
c000101
a101000
c000101
a101000
b010010
c000101 (列表4)

假设列表4中1的总个数为k，时间复杂度则为O(k+len(A))。
len(A)是对字符串A的预处理时间。
因为使用Unicode字符集，并且数据是随机产生，那么1的个数将十分稀疏。
所以称之为超稀疏LCS快速解法。其实对于字符集仅256个字符，
且均匀分布的字符串，本算法效率仍然不错。
但当字符集缩减到128个以下的时候，本算法将开始退化，
这时与基于二进制的快速LCS算法时间相当；
当字符集缩减到仅4个左右时，与经典DP相当，
直到仅一个字符时，将变为O(len(a)*len(b)+len(a)))，
变得比经典算法更慢一些，这是本算法的缺点。
不过对于本算法仍然可以使出一些小技巧可以保证绝不慢于经典DP。
但实际应用的话当你预测到1的个数会十分密集，并且字符集相当小的时候，
应该及时换另一种基于二进制的快速LCS算法。
基于二进制的快速LCS算法的预处理空间复杂度为O(len(a)*s)，
s为字符集大小。因为使用了二进制进行并行运算，不管1的个数稀疏与否，
均具有相当的并且非常快的速度（比普通的快一个数量级）。
但正因为在Unicode下s达到65536，
而len(a)最大可以100000，两者一相乘。。。
所以在大字符集下无法使用那个算法。

本算法对于长度为100000个字符，字符集为Unicode，
并且随机平均分布的字符串计算LCS长度，时间完全可以在1s以内。
在本人机器上实测为700ms左右，
若在P4 2.0GHz机器上估计200ms左右的时间就可以解决了。

关于LCS，的确有在实际问题中用得上的地方，
例如本人的论坛http://yzfy.org的改错题的判定就是用LCS的变形做的，
所以本人才会专心研究这个LCS。如果哪位有兴趣，
可以研究一下给你两段代码，判断出哪部分被修改过。
或者给出三段代码分别记为s,s1,s2，s是原代码，
s1,s2是两个不同的修改版本，要判断s1,s2修改过的部分有没有重合，
如果没有重合就把s1,s2修改的合并成一份代码（类似版本控制软件）。
前提是未知是什么语言所编写的代码。字符集为扩展ASCII。
注意代码可能会很长，上万行代码的话，文件大小约100Kb，
和本题有相当的数据长度吧。

On Jan 13, 9:05 pm, TCPIPer <TCPI...@gmail.com> wrote:
> 程序应该还有点问题丫：（