欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最长公共子序列模板

程序员文章站 2024-01-14 14:56:04
...
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#define maxn 1001
using namespace std;
char str1[maxn],str2[maxn];
int a[maxn][maxn];
int main()
{
    while(~scanf("%s%s",str1,str2))
	{
        int l1=strlen(str1);
        int l2=strlen(str2);
        for(int i=0;i<=l2;i++)
		a[0][i]=0;
        for(int i=0;i<=l1;i++)
		a[i][0]=0;
        for(int i=1;i<=l1;i++)
		{
            for(int j=1;j<=l2;j++)
			{
                if(str1[i-1]==str2[j-1])
                a[i][j]=a[i-1][j-1]+1;
                else
                a[i][j]=max(a[i-1][j],a[i][j-1]);
            }
        }
        printf("%d\n",a[l1][l2]);
    }
    return 0;
}

 

相关标签: 最长公共子序列