上次說，LCS有O(n^2 / logn)的解法。這個解法是在字符集不大的情況下，先預(yù)處理，再用位運算做狀態(tài)轉(zhuǎn)移。
唐文斌曾經(jīng)翻譯過一篇論文，專門討論這個問題。
應(yīng)richardxx的要求，我把那篇論文貼在這里：
基于位運算的最長公共子序列算法下面是練習(xí)題（n = 10000 的LCS）
http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1210和我的解答
#include <stdio.h>
#include <string.h>
#define WLEN 32
#define LOGWLEN 5
#define SMAX 16384
#define BITMAX 512
#define ALPHASIZE 128
typedef unsigned int WORD;
typedef char INDEX;
int nwords;
WORD bit1[BITMAX];
WORD bit2[BITMAX];
WORD a_strings[ALPHASIZE][BITMAX];
WORD *pb1,*pb2,*t1;
WORD bitmask[LOGWLEN]=
{0x55555555,0x33333333,0x0f0f0f0f,0x00ff00ff,0x0000ffff};
void alphastrings(INDEX *s,int len) {
register INDEX *p;
register int i,j;
for (i=0;i<ALPHASIZE;i++) for (j=0;j<nwords;j++) a_strings[i][j]=0;
p=s;
j=len;
for (i=0;i<j;i++) a_strings[*(p++)][i/WLEN]|=1<<(i%WLEN);
return;
}
void bitops(WORD *last,WORD *cur,INDEX index) {
register WORD x,y;
register int j;
register WORD *a_s;
register WORD top_borrow,bottombit;
a_s=&a_strings[index][0];
bottombit=1;
for (j=0;j<nwords;j++) {
y=*(last++);
x=y|*(a_s++);
top_borrow=(y>>(WLEN-1))&0x1;
y=((y<<1)|bottombit);
if (x<y) top_borrow=1;
*(cur++)=x&((x-y)^x);
bottombit=top_borrow;
}
return;
}
int bitcount(WORD *wp) {
register WORD w,count;
register int j,rshift,i;
count=0;
for (i=0;i<nwords;i++) {
w=*(wp++);
rshift=1;
for (j=0;j<LOGWLEN;j++) {
w=(w&bitmask[j])+((w&~bitmask[j])>>rshift);
rshift<<=1;
}
count+=w;
}
return count;
}
int bitlcs(INDEX *a,int lena,INDEX *b,int lenb) {
register int i;
register INDEX *pbstring;
register int j,k;
nwords=(lena+WLEN-1)/WLEN;
alphastrings(a,lena);
pb1=&bit1[0];
for (i=0;i<nwords;i++) *pb1++=0;
pb1=&bit1[0];
pb2=&bit2[0];
pbstring=b;
for (i=1;i<=lenb;i++) {
bitops(pb1,pb2,*(pbstring++));
t1=pb1; pb1=pb2; pb2=t1;
}
return bitcount(pb1);
}
int main() {
char sa[SMAX],sb[SMAX];
while (scanf("%s%s",sa,sb)!=EOF) printf("%d\n",bitlcs(sa,strlen(sa),sb,strlen(sb)));
return 0;
}