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


相关文章
|
10月前
|
Java
Leetcode 467. Unique Substrings in Wraparound String
大概翻译下题意,有个无限长的字符串s,是由无数个「abcdefghijklmnopqrstuvwxy」组成的。现在给你一个字符串p,求多少个p的非重复子串在s中出现了?
41 0
|
机器学习/深度学习
CF1552A Subsequence Permutation(string排序大法)
CF1552A Subsequence Permutation(string排序大法)
32 0
|
C++
【PAT甲级 - C++题解】1040 Longest Symmetric String
【PAT甲级 - C++题解】1040 Longest Symmetric String
57 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.
100 0
AT水题String Rotation
|
Python
Leetcode-Easy 796. Rotate String
Leetcode-Easy 796. Rotate String
62 0
Leetcode-Easy 796. Rotate String
|
人工智能 vr&ar
Atcoder--Candy Distribution II--前缀和+map
题目描述 There are N boxes arranged in a row from left to right. The i-th box from the left contains Ai candies. You will take out the candies from some consecutive boxes and distribute them evenly to M children. Such being the case, find the number of the pairs (l,r) that satisfy the following:
94 0
hdu 3336 Count the string
点击打开链接hdu 3336 思路:kmp+next数组的应用 分析: 1 题目要求的是给定一个字符串s,求字符串s的所有的前缀在s的匹配的次数之和mod10007. 2 很明显n1,为什么要从n开始而不是1开始呢,这里因为是要求前缀的匹配数而不是后缀; 4 求sum的时候注意每一步都有可能超过范围,所以就要求一次sum同时取模一次。
843 1