poj 1458 최장 공통 서열

758 단어
제목: 두 문자열의 가장 긴 공통 서열을 구합니다.
사고방식: 동적 기획 + 스크롤 그룹
#include <stdio.h>
#include <string.h>
#define N 1025
int dp[2][N];
char s[N],t[N];
int max(int a,int b){
	if(a>b)
		return a;
	return b;
}
int common_subsequence(){
	int i,j,lens,lent;
	lens = strlen(s+1);
	lent = strlen(t+1);
	for(i = 1;i<=lens;i++){
		for(j = 1;j<=lent;j++)
			if(s[i] == t[j])
				dp[1][j] = dp[0][j-1]+1;
			else
				dp[1][j] = max(dp[0][j],dp[1][j-1]);
		for(j = 1;j<=lent;j++)
			dp[0][j] = dp[1][j];
	}
	return dp[1][lent];
}
int main(){
	freopen("a.txt","r",stdin);
	while(scanf("%s %s",s+1,t+1)!=EOF){
		memset(dp,0,sizeof(dp));
		printf("%d
",common_subsequence()); } return 0; }

좋은 웹페이지 즐겨찾기