spoj EDIST dp string distance

简介:

http://www.spoj.com/problems/EDIST/


#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int f[2002][2002];
char a[2002], b[2002];
int main(){
	int t;
	scanf("%d", &t);
	while (t--){
		memset(f, 127 / 3, sizeof(f));
		scanf("%s%s", a, b);
		int n = strlen(a), m = strlen(b);
		for (int i = 0; i < n; i++) f[i][0] = i;/////
		for (int i = 0; i < m; i++) f[0][i] = i;/////
		for (int i = 1; i <= n; i++)
		    for (int j = 1; j <= m; j++){
    			if (a[i-1] == b[j-1]) f[i][j] = f[i-1][j-1];
		        else f[i][j] = min(min(f[i-1][j], f[i][j-1]), f[i-1][j-1]) + 1;
    		}		        
        printf("%d\n", f[n][m]);
	}
	return 0;
}


相关文章
|
Java
Leetcode 467. Unique Substrings in Wraparound String
大概翻译下题意,有个无限长的字符串s,是由无数个「abcdefghijklmnopqrstuvwxy」组成的。现在给你一个字符串p,求多少个p的非重复子串在s中出现了?
46 0
|
机器学习/深度学习
CF1552A Subsequence Permutation(string排序大法)
CF1552A Subsequence Permutation(string排序大法)
37 0
CF489C Given Length and Sum of Digits
CF489C Given Length and Sum of Digits
AtCoder Beginner Contest 225 F.String Cards(dp)
AtCoder Beginner Contest 225 F.String Cards(dp)
88 0
codeforces1426——F. Number of Subsequences(DP)
codeforces1426——F. Number of Subsequences(DP)
104 0
AT水题String Rotation
题目描述 You are given string S and T consisting of lowercase English letters. Determine if S equals T after rotation. That is, determine if S equals T after the following operation is performed some number of times: Operation: Let S=S1S2…S|S|. Change S to S|S|S1S2…S|S|−1.
104 0
AT水题String Rotation
ZOJ - Problem Set - 3985 String of CCPC
ZOJ - Problem Set - 3985 String of CCPC
96 0