복 단 14 대학원 시험 문제 (2) - 두 문자열 의 편집 거 리 를 계산 합 니 다.

9312 단어 시험 문제알고리즘
제목: 두 문자열 을 같은 세 가지 기본 동작 으로 정의 합 니 다.
  • 문자 수정 (예 를 들 어 a 를 b 로 바 꾸 는 것)
  • 한 글자 추가 (예 를 들 어 abed 가 abed 로 변 함)
  • 한 글자 삭제 (예 를 들 어 jackblog 가 jackblog 로 변 함)
    • 잭 블 로그 에서 잭 블 로그 까지 는 하 나 를 삭제 하거나 l 을 추가 하면 두 문자열 을 동일 하 게 만 들 수 있 습 니 다.이 작업 에 필요 한 최소 횟수 를 두 문자열 의 편집 거리 L 로 정의 합 니 다.프로그램 을 작성 하여 지정 한 파일 의 문자열 거 리 를 계산 합 니 다.512 바이트 이상 의 길이 의 ASCII 문자열 을 입력 하고 화면 에 문자열 의 편집 거 리 를 출력 합 니 다.입력 샘플
    Hello world! 
Hello word!

    출력 샘플
    1

    #include
#include
using namespace std;
string a, b;
int dp[520][520];
int min(int a, int b, int c) {
	if (a <= b && a <= c)
		return a;
	else if (b <= a && b <= c)
		return b;
	else
		return c;
}
int main() {
	getline(cin, a);
	getline(cin, b); 
	int lenA = a.length();
	int lenB = b.length();
	for (int i = 0; i < lenA; i++) dp[i][0] = i;
	for (int j = 0; j < lenB; j++) dp[0][j] = j;
	for (int i = 1; i < lenA; i++) {
		for (int j = 1; j < lenB; j++) {
			if (a[i] == b[j])
				dp[i][j] = dp[i - 1][j - 1];
			else
				dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1, dp[i][j - 1] + 1);
		}
	}
	printf("%d", dp[lenA - 1][lenB - 1]);
	return 0;
}
    데이터 구조 순환 대기 열의 실현
    유형 피쳐는 어떻게 사용합니까?

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage