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).
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.
1 5 2 656 67 9313 1178 38 87 1 9509 1
Case #1: 1 0
思路：编辑距离的基础题，题目说的很麻烦，我英文不好看了半天才看懂。。。第一遍TLE，加了个剪枝才AC
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
char a[1505][15],b[15];
int ans[15][15];
int s[1005];
int main()
{
int n,i,m,k=1,j,t,r,p,q,x,y,u; //k作为case数,s作为结果 r为界限
scanf("%d",&t);
while(t--)
{
memset(s,0,sizeof(s));
scanf("%d%d",&n,&m);
for(i=0;i<n;i++) scanf("%s",a[i]);
for(i=0;i<m;i++)
{
scanf("%s%d",b,&r);
for(j=0;j<n;j++)
{
y=strlen(a[j]);
u=strlen(b);
if(abs(y-u)>r) continue; //防TLE剪枝
for(p=0;p<=y;p++)
ans[p][0]=p;
for(p=0;p<=u;p++)
ans[0][p]=p;
for(p=0;p<y;p++)
for(q=0;q<u;q++)
{
x=(a[j][p]!=b[q]);
ans[p + 1][q + 1] = min(ans[p][q] + x, min(ans[p][q + 1] + 1, ans[p + 1][q] + 1));
}
if(ans[y][u]<=r) s[i]++;
}
}
printf("Case #%d:\n",k++);
for(i=0;i<m;i++) printf("%d\n",s[i]);
}
return 0;
}