sdut 1225 편집 거리 (dp)
2530 단어 dp
제목 설명
문자열의 기본 동작은 한 문자를 삭제하고, 한 문자를 삽입하고, 한 문자를 다른 문자로 수정하는 세 가지입니다.
우리는 상술한 세 가지 조작을 한 번 진행한 임의의 조작을 일차 문자의 기본 조작이라고 부른다.
다음에 우리는 두 문자열의 편집 거리를 정의한다. 두 문자열 a와 b에 대해 상술한 기본 조작을 통해 우리는 a를 b 또는 b로 a로 바꿀 수 있다. 그러면 문자열 a를 문자열 b로 바꾸는 데 필요한 최소 기본 문자 조작 단계를 문자열 a와 문자열 b의 편집 거리라고 한다.
예를 들어 a="ABC", b="CBCD"는 a와 b의 편집 거리가 2이다.
임의의 두 문자열의 편집 거리를 계산하는 빠른 프로그램을 만드는 것이 당신의 임무입니다.
입력
여러 그룹의 테스트 데이터를 포함하는 것을 입력하십시오.각 그룹의 테스트 데이터 행은 문자열 A와 문자열 B입니다.
문자열의 길이는 1024보다 크지 않고 모두 자모입니다.
출력
거리를 편집합니다.
샘플 입력
ABC CBCD샘플 출력
2처음에는 생각이 없었지만 가장 긴 공공 서열을 구하는 것과 약간 유사하다고 느꼈다.선배의 말을 듣고 나서야 생각이 났다.
초기화 문제 때문에 웨이를 몇 번 했어요.초기화는 0부터 시작해야 합니다.
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[1100][1100];
int main()
{
char s1[1100],s2[1100];
while(~scanf("%s",s1))
{
scanf("%s",s2);
int len1 = strlen(s1);
int len2 = strlen(s2);
memset(dp,0,sizeof(dp));
for(int i = 0; i <= len2; i++)
dp[0][i] = i;
for(int i = 0; i <= len1; i++)
dp[i][0] = i;
for(int i = 1; i <= len1; i++)
{
for(int j = 1; j <= len2; j++)
{
if(s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1];
else //i j ， ， ， ，
dp[i][j] = min(dp[i-1][j-1]+1, min(dp[i][j-1]+1,dp[i-1][j]+1));
}
}
printf("%d
",dp[len1][len2]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
