HDU 4323 Magic Number 편집 거리

제목 설명:

Description There are many magic numbers whose lengths are less than 10. Given some queries, each contains a single number, if the Levenshtein distance (see below) between the number in the query and a magic number is no more than a threshold, we call the magic number is the lucky number for that query. Could you find out how many luck numbers are there for each query?
Levenshtein distance (from Wikipedia http://en.wikipedia.org/wiki/Levenshtein_distance): In information theory and computer science, the Levenshtein distance is a string metric for measuring the amount of difference between two sequences. The term edit distance is often used to refer specifically to Levenshtein distance. The Levenshtein distance between two strings is defined as the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character. It is named after Vladimir Levenshtein, who considered this distance in 1965. For example, the Levenshtein distance between “kitten” and “sitting” is 3, since the following three edits change one into the other, and there is no way to do it with fewer than three edits: 1.kitten → sitten (substitution of ‘s’ for ‘k’) 2.sitten → sittin (substitution of ‘i’ for ‘e’) 3.sittin → sitting (insertion of ‘g’ at the end).
Input There are several test cases. The first line contains a single number T shows that there are T cases. For each test case, there are 2 numbers in the first line: n (n <= 1500) m (m <= 1000) where n is the number of magic numbers and m is the number of queries. In the next n lines, each line has a magic number. You can assume that each magic number is distinctive. In the next m lines, each line has a query and a threshold. The length of each query is no more than 10 and the threshold is no more than 3.
Output For each test case, the first line is “Case #id:”, where id is the case number. Then output m lines. For each line, there is a number shows the answer of the corresponding query.
Sample Input

1
5 2
656
67
9313
1178
38
87 1
9509 1 

Sample Output

Case #1:
1
0 

제목 분석:

n개의 문자열을 주고 m팀에게 물어보는 것입니다. 각 그룹의 질문에는 하나의 문자열 s와 하나의 숫자 x가 포함되어 있습니다. 상기 n개의 문자열과 이 문자열 s의 편집 거리가 x와 같은 문자열 개수보다 작음을 구하십시오.고전적인 DP 편집 거리 제목은 51nod에 편집 거리 강좌가 있는데 가서 볼 수 있어요. 아주 잘했어요.전송문: 그리고 이 세트 코드는 AC입니다.나는 또 한 편의 박문도 편집 거리이다.

코드는 다음과 같습니다.

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const double eps = 1e-4;
const int MAXN=1550;

char a[MAXN][20];
int n,m;
int T;

int DP(char *s1,char *s2)
{
    int dp[15][15];
    int len1=strlen(s1),len2=strlen(s2);
    memset(dp,0,sizeof(dp));
    for(int i=0; i<=len1; i++) dp[i][0]=i;
    for(int j=0; j<=len2; j++) dp[0][j]=j;
    for(int i=1; i<=len1; i++)
    {
        for(int j=1; j<=len2; j++)
        {
            dp[i][j]=min(dp[i-1][j] , dp[i][j-1]) + 1;
            dp[i][j]=min(dp[i][j] , dp[i-1][j-1] + (s1[i-1] != s2[j-1]));
        }
    }
    return (dp[len1][len2]);
}
int main()
{
    scanf("%d",&T);
    for(int t=1; t<=T; t++)
    {
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++) scanf("%s",a[i]+1);
        char s[15];
        int x;
        printf("Case #%d:
",t);
        for(int i=1; i<=m; i++)
        {
            scanf(" %s %d",s+1,&x);
            int ans=0;
            for(int j=1; j<=n; j++)
            {
                int len1=strlen(s+1);
                int len2=strlen(a[j]+1);
                if (abs(len1-len2)>x) continue;
                if (DP(s+1,a[j]+1)<=x) ans++;
            }
            printf("%d
",ans);
        }
    }
    return 0;
}