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;
}


相关文章
CF1553B Reverse String(数学思维)
CF1553B Reverse String(数学思维)
51 0
|
Java
Leetcode 467. Unique Substrings in Wraparound String
大概翻译下题意,有个无限长的字符串s,是由无数个「abcdefghijklmnopqrstuvwxy」组成的。现在给你一个字符串p,求多少个p的非重复子串在s中出现了?
63 0
|
机器学习/深度学习
CF1552A Subsequence Permutation(string排序大法)
CF1552A Subsequence Permutation(string排序大法)
45 0
|
机器学习/深度学习
CF71A Way Too Long Words(string简单模拟)
CF71A Way Too Long Words(string简单模拟)
78 0
|
C++
【PAT甲级 - C++题解】1040 Longest Symmetric String
【PAT甲级 - C++题解】1040 Longest Symmetric String
76 0
codeforces1426——F. Number of Subsequences(DP)
codeforces1426——F. Number of Subsequences(DP)
118 0
|
存储 缓存 Java
String s = new String("xyz")创建了几个实例你真的能答对吗?
String s = new String("xyz")创建了几个实例你真的能答对吗?
202 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.
112 0
AT水题String Rotation
HDOJ(HDU) 1708 Fibonacci String
HDOJ(HDU) 1708 Fibonacci String
105 0