HDu 4323 Magic Number(最短編集距離)
5169 ワード
Magic Number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1404 Accepted Submission(s): 589
Problem 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
Sample Output
タイトル:
辞書を1つ与えて、それからm個の質問をして、毎回1つの文字列と1つのkを与えて、辞書の中でこの文字列と最も短い編集距離がkより小さいものがどれだけあるかを探し出します.(2つの文字列の最短編集距離:1つの文字列が
挿入、削除、置換
少なくとも数ステップで別の文字列に変更する必要があります)
考え方:
本体の複雑さは私が下げていないで、906 msは線を拭いて==を過ぎて、辞書を列挙してからdpが最短の編集距離を求めるたびに十分です.
dp初期化はdp[0][j]、dp[i][0]ともに意味があり、INFではなくWAが開始されたことを覚えておいてください.
s 1、s 2の文字列.
dp[i][j] i-s 1の位置 j-s 2の位置 dp-少なくとも数回操作して前のものを同じにすることができます
if(s1[i]==s2[j]) dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]+1,dp[i][j-1]+1);
else dp[i][j]=min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1;
コード:
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1404 Accepted Submission(s): 589
Problem 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
タイトル:
辞書を1つ与えて、それからm個の質問をして、毎回1つの文字列と1つのkを与えて、辞書の中でこの文字列と最も短い編集距離がkより小さいものがどれだけあるかを探し出します.(2つの文字列の最短編集距離:1つの文字列が
挿入、削除、置換
少なくとも数ステップで別の文字列に変更する必要があります)
考え方:
本体の複雑さは私が下げていないで、906 msは線を拭いて==を過ぎて、辞書を列挙してからdpが最短の編集距離を求めるたびに十分です.
dp初期化はdp[0][j]、dp[i][0]ともに意味があり、INFではなくWAが開始されたことを覚えておいてください.
s 1、s 2の文字列.
dp[i][j] i-s 1の位置 j-s 2の位置 dp-少なくとも数回操作して前のものを同じにすることができます
if(s1[i]==s2[j]) dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]+1,dp[i][j-1]+1);
else dp[i][j]=min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1;
コード:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 1005
#define MAXN 2005
#define mod 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;
int n,m,k,ans,cnt,tot,flag;
char s[1505][15],len[1505],ts[15];
int dp[15][15];
void solve()
{
int i,j,p,t,length=strlen(ts+1);
ans=0;
for(p=1; p<=n; p++)
{
if(abs(len[p]-length)>k) continue ;
memset(dp,0x3f,sizeof(dp));
for(i=0;i<=length;i++)
{
dp[0][i]=i;
}
for(j=0;j<=len[p];j++)
{
dp[j][0]=j;
}
for(i=1; i<=len[p]; i++)
{
for(j=1; j<=length; j++)
{
if(s[p][i]==ts[j]) dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j]+1,dp[i][j-1]+1));
else
{
dp[i][j]=min(dp[i][j-1],min(dp[i-1][j],dp[i-1][j-1]))+1;
}
}
}
if(dp[len[p]][length]<=k) ans++;
}
}
int main()
{
int i,j,t,test=0;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=1; i<=n; i++)
{
scanf("%s",s[i]+1);
len[i]=strlen(s[i]+1);
}
printf("Case #%d:
",++test);
while(m--)
{
scanf("%s%d",ts+1,&k);
solve();
printf("%d
",ans);
}
}
return 0;
}
/*
1
5 2
656
67
9313
1178
38
87 1
9509 1
*/