编辑距离问题

作者:czp 分类: PAT 发布于:2016-12-28 14:08 ė590次浏览 60条评论
Time limit: 1000MS    Memory limit: 32768K 
Total Submit: 57    Accepted: 41 

两个字符串的编辑距离(Edit distance)指的是将两个字符串上下排列时,其字母不同的列数的最小值。由于对齐的方式不同,不同字母的列数也不同,而这个不同列数的最小值才是编辑距离。初学算法的同学,对于理解编辑距离有一定困难,但编辑距离的实际意义是将一个字符串修改成另一个字符串所需要的最小编辑动作,这里的编辑动作包括插入、删除和字符替换。现在给你两个字符串,请你算算这两个字符串的编辑距离。

输入说明:

本问题有多组测试数据,输入的第一行就是测试数据的组数n1<=n<=20),对于每一组测试数据,有两行,每一行是一个字符串(1<=字符串长度<=1000)。

输出说明:

对于每一组输入,对应的输出只有一个整数,就是输入的两个字符串的编辑距离。

Sample Input:

1

ABDCRHGWDWSDSKJDSKDFHJKFDKJDSAFKJFDAKFDSAJFDKASDJLFLDKF

ERUDSHDFHGFLKGFGFKGFLKSAEWALUTRHGFKIFDGITRMDFLKDSLSDLLEHJFKLEKIREFMFK

 

Sample Output:

53


#include<iostream>

using namespace std;

#define MAX_SIZE 1001

void print_array(int array[MAX_SIZE][MAX_SIZE], int x, int y) {
    int i, j;
    for (i = 0; i <= x; i++) {
        for (j = 0; j <= y; j++) {
            cout << array[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

int get_max_edit_length(string string1, string string2) {
    int array[MAX_SIZE][MAX_SIZE];
    int i, j;
    int min1, min2, min3, min;

    for (i = 0; i <= string1.size(); i++) {
        array[i][0] = i;
    }
    for (j = 0; j <= string2.size(); j++) {
        array[0][j] = j;
    }

    for (i = 1; i <= string1.size(); i++) {
        for (j = 1; j <= string2.size(); j++) {
            min1 = (string2[j - 1] == string1[i - 1]) ? array[i - 1][j - 1] : (array[i - 1][j - 1] + 1);
            min2 = array[i][j - 1] + 1;
            min3 = array[i - 1][j] + 1;

            min = min1 < min2 ? min1 : min2;
            min = min < min3 ? min : min3;
            array[i][j] = min;
            //print_array(array, string1.size(), string2.size());
        }
    }

    return array[string1.size()][string2.size()];
}

int main() {
    int n;
    string string1, string2;
    cin >> n;

    while (n--) {
        cin >> string1;
        cin >> string2;
        cout << get_max_edit_length(string1, string2) << endl;
    }

    return 0;
}

本文出自 czp的装逼站,转载时请注明出处及相应链接。

0

发表评论

电子邮件地址不会被公开。必填项已用*标注


Ɣ回顶部