此程序仅用于英文字串，输入还得改，占个地方。
[code=c]
/*Input the length of the two string(m&n):
8 7
Input the first string:
a b c b d a b
Input the second string:
b d c a b a
Press any key to continue
*/
#include<iostream>
using namespace std;

void LcsLength(char *x,char *y,int *c[],int m,int n)
{
    for(int i=0;i<m;i++)
        c[i][0]=0;
    for(int j=0;j<n;j++)
        c[0][j]=0;
    for(i=1;i<m;i++)
    {
        for(j=1;j<n;j++)
        {
            if(x[i]==y[j])
            {
                c[i][j]=c[i-1][j-1]+1;
            }
            else if(c[i-1][j]>=c[i][j-1])
            {
                c[i][j]=c[i-1][j];
            }
            else
            {
                c[i][j]=c[i][j-1];
            }
        }
    }
}

int main()
{
    int i,j;
    int m,n;
    int l,k;
    cout<<"Input the length of the two string(l&k):"<<endl;
//    cin>>m>>n;
    cin>>l>>k;
    m=l+1;
    n=k+1;
    char *x,
        *y;
    x=new char[m];
    y=new char[n];
    cout<<"Input the first string:"<<endl;
    for(i=1;i<m;i++)
        cin>>x[i];
    cout<<"Input the second string:"<<endl;
    for(j=1;j<n;j++)
        cin>>y[j];
    int **c;
    c=new int*[m];
    for(i=0;i<m;i++)
        c[i]=new int[n];
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
            c[i][j]=0;
    }
    LcsLength(x,y,c,m,n);
    int max=c[l][k];
    cout<<max<<endl;
    delete [] x;
    x=NULL;
    delete [] y;
    y=NULL;
    for(i=0;i<m;i++)
        delete []c[i];
    delete []c;
    c=NULL;
    return 0;
}
[/code]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
unsigned char a[200001],b[200001];
int **p,str1[200001],str2[200001];
int main(){
  int l1,l2,i,j,sum;
  while(scanf("%s %s",a,b)!=EOF){
    for(i=0,l1=0,l2=0,j=0;a[i]&&b[j];){
      if(a[i]>127&&a[i+1]>127){
        str1[l1++]=a[i]*1000+a[i+1];
        i+=2;
      }
      else{
        str1[l1++]=a[i];
        i++;
      }
      if(b[j]>127&&b[j+1]>127){
        str2[l2++]=b[j]*1000+b[j+1];
        j+=2;
      }
      else{
        str2[l2++]=b[j];
        j++;
      }
    }
    if(a[i]){
      while(a[i]){
        if(a[i]>127&&a[i+1]>127){
        str1[l1++]=a[i]*1000+a[i+1];
        i+=2;
      }
      else{
        str1[l1++]=a[i];
        i++;
      }}
    }
    else if(b[j]){
      while(b[j]){
        if(b[j]>127&&b[j+1]>127){
        str2[l2++]=b[j]*1000+b[j+1];
        j+=2;
      }
      else{
        str2[l2++]=b[j];
        j++;
      }}
    }
    p=(int**)malloc(sizeof(int*)*(l1+1));
    p[0]=(int*)malloc(sizeof(int)*(l2+1));
    memset(p[0],0,sizeof(int)*(l2+1));
    for(i=1;i<=l1;i++){
      p[i]=(int*)malloc(sizeof(int)*(l2+1));
      p[i][0]=0;
    }
    for(i=1;i<=l1;i++)
      for(j=1;j<=l2;j++){
        if(str1[i-1]==str2[j-1])
          p[i][j]=p[i-1][j-1]+1;
        else if(p[i-1][j]>=p[i][j-1])
          p[i][j]=p[i-1][j];
        else
          p[i][j]=p[i][j-1];
      }
    printf("%d\n",p[l1][l2]);
    delete p;
  }
  return 0;
}

[code=c]
#include <iostream>
using namespace std;

#define M(x,y) x>y?x:y

int Maxset(char* s1,char *s2)
{
    if(*s1==0||*s2==0)
        return 0;
    if(*s1==*s2)
        return 1+Maxset(++s1,++s2);
    else
    {
        char *p1=s1;
        char *p2=s2;
        int i=Maxset(++p1,s2);
        int j=Maxset(s1,++p2);
        return M(i,j);
    }
}

int main()
{
    char s1[100],s2[100];
    while(gets(s1)&&gets(s2))
    {
        cout<<Maxset(s1,s2)<<endl;
    }
    return 0;
}[/code]

[code]
#include <stdio.h>
#include <string.h>
#define L 200000
int c[2][L];
int
lcsl(const char * s1,int s1l,const char * s2,int s2l)
{
    int i,j,xl,yl,yy=0;
    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(1){
        fscanf(stdin,"%s%s",x,y);
        fprintf(stdout,"%d\n",lcsl(x,strlen(x),y,strlen(y)));
    }
    return 0;
}

[/code]
:PP

看看

看看答案！！！

如果某一组本身有重复的字符，怎么处理？

#include <iostream>
using namespace std;

void main(void)
{
    cout<<"Input the first string.."<<endl;
    unsigned char arr[200000][2],brr[200000][2];   //第二位：0、半角；1、全角前半；2、全角后半
    unsigned long i=0,s_arr=0,j=0,s_brr=0,s_add=0;
    //------------------------------------------------
    while(1)  
    {
        cin>>arr[i][0];
        if(arr[i][0]=='#')
            break;
        i++;
        s_arr++;
    }
    cout<<"Input the second string.."<<endl;
    while(1)  
    {
        cin>>brr[j][0];
        if(brr[j][0]=='#')
            break;
        j++;
        s_brr++;
    }
    //------------------------------------------------
    if(arr[0][0]>127)   arr[0][1]=1;
    else                arr[0][1]=0;
    for(i=1;i<s_arr;i++)
    {
        if(arr[i][0]>127)
        {
            if(arr[i-1][1]==1)          arr[i][1]=2;
            else if(arr[i+1][0]>127)    arr[i][1]=1;
            else                        arr[i][1]=0;
        }
        else                            arr[i][1]=0;
    }
    //------------------------------------------------
    if(brr[0][0]>127)   brr[0][1]=1;
    else                brr[0][1]=0;
    for(j=1;j<s_brr;j++)
    {
        if(brr[j][0]>127)
        {
            if(brr[j-1][1]==1)          brr[j][1]=2;
            else if(brr[j+1][0]>127)    brr[j][1]=1;
            else                        brr[j][1]=0;
        }
        else                            brr[j][1]=0;
    }

    unsigned long tempj=0;        //第二组有相同字符时的位置
    for(i=0;i<s_arr;i++)
    for(j=tempj;j<s_brr;j++)
    {
        if(arr[i][1]==brr[j][1])
        {
            if(arr[i][1]==0 && arr[i][0]==brr[j][0])  
            {  
                s_add++;  
                tempj=j+1; 
                break;
            }
            if(arr[i][1]==1 && arr[i][0]==brr[j][0] && arr[i+1][0]==brr[j+1][0])
            {
                s_add++;
                tempj=j+2;
                break;
            }    
        }
    }

    cout<<"s_add is "<<s_add<<endl;     //答案
    cout<<"s_arr is "<<s_arr<<endl;     //第一组的长度
    cout<<"s_brr is "<<s_brr<<endl;     //第二组的长度


    return;
}

有一个问题就是我用while(cin>>arr[i][0])用来结束输入总是出问题（输入CTRL+Z结束），所以我改为用'#'号来结束输入。
请点评，谢谢！

#include <iostream>
#include <ctime>
using namespace std;

int MaxLen(unsigned short x[],unsigned short y[],int lenx,int leny)
{
    unsigned short *px,*py; //分别指向长短数组
    int *plx,*ply;            //长短数组的长度指针
    int *c0;                //矩阵
    int *c1;
    int j = 0;
    //寻找短数组
    if(lenx>leny)
    {
        px = x;
        py = y;
        plx = &lenx;
        ply = &leny;
    }
    else
    {
        px = y;
        py = x;
        plx = &leny;
        ply = &lenx;
    }
    //初始化
    c0 = new int [*ply + 1];
    c1 = new int [*ply + 1];

    for (j=0;j<*ply + 1;j++)
        c0[j] = c1[j] = 0;

    
    //计算
    //  if(x[i] = y[j]) c[i][j] = c[i-1][j-1] + 1
    //  else
    //      c[i][j] = max(c[i][j-1],c[i-1][j])
    
    for(int i=1;i<=*plx;i++)
    {
        for(j=1;j<=*ply;j++)
        {
            if(px[i-1] == py[j-1])
                c1[j] = c0[j-1] + 1;
            else
                c1[j] = (c1[j-1] > c0[j] ? c1[j-1] : c0[j]);
        }
        for(j=0;j<=*ply;j++)
        {
            c0[j] = c1[j];
        }
    }
    return c1[*ply];
}

int main(void)
{
    unsigned short x[200000] = {0}; //存储转换字符串X
    unsigned short y[200000] = {0}; //存储转换字符串Y
    int lenx = 0,leny = 0;            //X Y 长度
    unsigned char c = 0,pro = 0;    //当前读取字符 前一个字符
    bool bU = false;                //全角标记
    int words = 0;                    //字符串数
    unsigned short *p = x;            //指针
    int *plen = &lenx;
    
    while(c = unsigned(cin.get()))
    {
        //当前字符 > 127
        if(c>127)  
        {    
            //前一个字符 > 127
            //作为全角字符入数组
            if(bU)  
            {
                p[*plen] = c * pro;
                (*plen) ++;
                bU = false;
            }
            //前一字符 < 127
            //暂存并作标记
            else    
            {
                pro = c;
                bU = true;
            }
        }
        //半角字符处理
        else if(c>32)
        {
            //前一个字符 > 127 
            //前一字符入数组
            if(bU)  
            {
                p[*plen] = pro;
                (*plen) ++;
                bU = false;
            }
            //当前字符入数组
            p[*plen] = c;
            (*plen) ++;

        }
        //特殊字符处理
        else
        {
            //前一个字符 > 127 
            //前一字符入数组
            if(bU)  
            {
                p[*plen] = pro;
                (*plen) ++;
                bU = false;
            }
            //处理间隔符、结束符
            if(char(c) == '\n' || char(c) == ' ' || char(c) == EOF)
            {
                words ++;
                if(words & 1)
                {
                    p = y;
                    plen = &leny;
                }
                else
                {
                    p = x;
                    plen = &lenx;
                    cout<<MaxLen(x,y,lenx,leny)<<'\n';
                    lenx = leny = 0;
                }
            }
            if(char(c) == EOF)
                break;
        }
    }
    /*
    srand(   (unsigned)time(   NULL   )   );   
    while(true){
    for(int i=0;i<200000;i++)
    {
        x[i] = rand() % 60000;
        y[i] = rand() % 60000;
    }
    lenx = rand() % 10000 + 190000;
    leny = rand() % 5000 + 150000;
    cout<< lenx<<"  "<<leny<<endl;
    cout<<MaxLen(x,y,lenx,leny)<<endl;
    cin>>c;}*/
    return 0;
}

[code=c]
#include <stdio.h>
#include <string.h>
#include <malloc.h>

#define MAX_LEN 200001

int x[MAX_LEN], y[MAX_LEN];

int LCS(char *a, char *b)
{
    int m = strlen(a) - 1, n = strlen(b) - 1;
    int i, j, size = sizeof(int) * (n + 2); //上面减的1加上+1空字符
    
    memset(x, 0, size);                //加这2句避免逐位循环填0
    memset(y, 0, size);                        

    for (i=m; i>=0; --i)
    {
        for (j=n; j>=0; --j)
        {
            if (a[i]==b[j])
            {
                if (a[i]>0 || (a[i]<0 && a[i-1]==b[j-1]))
                    x[j] = 1 + y[j+1];      //ASCII和汉字2字节都相等则添加
                else
                    x[j] = y[j] > x[j+1] ? y[j] : x[j+1];
                if (a[i]<0)
                    x[--j] = x[j+1];        //b串中如是汉字当作整体
            }
            else
            {
                x[j] = y[j] > x[j+1] ? y[j] : x[j+1];
                if (b[j]<0)
                    x[--j] = x[j+1];        //b串中如是汉字当作整体
            }
        }

        if (a[i]<0)                         //a串中如是汉字当作整体
            --i;
        memcpy(y, x, size);                 //复制x到y
    }

    return x[0];
}

int main()
{
    char s1[MAX_LEN], s2[MAX_LEN];

    while (gets(s1)!=NULL)
    {
        gets(s2);
        printf("%d\n", LCS(s1, s2));
    }

    return 0;
}
[/code]


说明：
1、基于DP的解法，时间复杂度O(mn)，空间复杂度O(2n);
2、用memset代替逐位循环填充a[i]==0||b[i]==0，可以快8％左右;
3、辅助的int数组x、y声明成全局变量，相比用new动态声明，在字串很短的时候经测试空间只多占8K左右(总共608K)，字串长时两种方式空间就没多大区别了，20万字长时内存总共占用2.5M左右。速度上动态声明的更慢;
4、如果20万长度的字串，时间要270多秒(2.8G 1G RAM)，对于1000ms的要求无论如何是达不到，所以代码姑且贴上。