浙江财经大学
信工学院ACM集训队

最长公共子序列

本文由 Ocrosoft 于 2016-12-19 12:16:07 发表
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
#define  rep(a,v,b) for(int a=v;a<b;a++)
#define  repe(a,v,b) for(int a=v;a<=b;a++)
#define MAXLEN 100
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 300000+ 10;
const int MOD = 1000000009;
int gcd(int a, int b)
{
	if (!b)return a;
	return gcd(b, a%b);
}
/*(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
/*(◕‿‿◕) 签订契约,成为马猴烧酒吧! (◕‿‿◕)*/
/*(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
using namespace std;
void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN])
{
	for(int i = 0; i <= m; i++)c[i][0] = 0;
	for(int j = 1; j <= n; j++)c[0][j] = 0;//1...i==0||j==0=>c[i][j]=0;
	for(int i = 1; i<= m; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			if(x[i-1] == y[j-1])//2...i,j>0&&x[i]==y[i]=>c[i][j]=c[i-1][j-1]+1
			{
				c[i][j] = c[i-1][j-1] + 1;
				b[i][j] = 0;//回溯左上(子问题)
			}
			else if(c[i-1][j] >= c[i][j-1])//3...i,j>0&&x[i]!=y[i]=>c[i][j]=max(c[i,j-1],c[i-1][j])
			{
				c[i][j] = c[i-1][j];
				b[i][j] = 1;//回溯左(子问题)
			}
			else
			{
				c[i][j] = c[i][j-1];
				b[i][j] = -1;//回溯上(子问题)
			}
		}
	}
	printf("%d\n",c[m][n]);
}

void PrintLCS(int b[][MAXLEN], char *x, int i, int j)
{
	if(i == 0 || j == 0)return;
	if(!b[i][j])//0
	{
		PrintLCS(b, x, i-1, j-1);
		printf("%c", x[i-1]);
	}
	else if(b[i][j] == 1)PrintLCS(b, x, i-1, j);
	else PrintLCS(b, x, i, j-1);
}

int main()
{
	char x[MAXLEN] = {"ABCBDAB"};
	char y[MAXLEN] = {"BDCABA"};
	int b[MAXLEN][MAXLEN];
	int c[MAXLEN][MAXLEN];
	int m=strlen(x), n=strlen(y);
	LCSLength(x, y, m, n, c, b);
	PrintLCS(b, x, m, n);
	printf("\n");
	return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » 最长公共子序列

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址