Вычисление редакционного расстояния: реализация на C++

C++   5 Апрель 2014  Автор статьи:  

Подробное описание алгоритма приведено в этой статье.

Данная программа читает со стандартного ввода две строки, редакционное расстояние между которыми требуется найти. В первую строку стандартного вывода программа выводит редакционное расстояние d между строками, а в следующие d строк – искомое редакционное предписание. Используются следующие обозначения операций:
1) INSERT i ch – вставить в позицию i символ ch.
2) DELETE i – удалить символ, находящийся в позиции i.
3) REPLACE i ch – заменить символ, находящийся в позиции i, символом ch.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

const int INF = 1E9;
const int LEN = 1000;
int d[LEN + 1][LEN + 1];
int p[LEN + 1][LEN + 1];

int main()
{
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    int l1 = s1.length();
    int l2 = s2.length();
    d[l1][l2] = 0;
    for (int i = l1; i >= 0; --i)
        for (int j = l2; j >= 0; --j)
        {
            if (i == l1 && j == l2)
                continue;
            d[i][j] = INF;
            if (i < l1 && j < l2 && s1[i] == s2[j])
            {
                d[i][j] = d[i + 1][j + 1];
                p[i][j] = 3;
            }
            if (i + 1 <= l1)
            {
                if (d[i + 1][j] + 1 < d[i][j])
                {
                    d[i][j] = d[i + 1][j] + 1;
                    p[i][j] = 0;
       
                }
            }
            if (i + 1 <= l1 && j + 1 <= l2)
            {
                if (d[i + 1][j + 1] + 1 < d[i][j])
                {
                    d[i][j] = d[i + 1][j + 1] + 1;
                    p[i][j] = 1;
                }
            }
            if (j + 1 <= l2)
            {
                if (d[i][j + 1] + 1 < d[i][j])
                {
                    d[i][j] = d[i][j + 1] + 1;
                    p[i][j] = 2;
                }
            }
        }
    cout << d[0][0] << endl;
    int curi = 0, curj = 0;
    int ch = 0;
    while (curi < l1 || curj < l2)
    {
        switch (p[curi][curj])
        {
        case 0:
            {
                cout << "DELETE " << curi + ch <<endl;
                ++curi;
                --ch;
                break;
            }
        case 1:
            {
                cout << "REPLACE " << curi + ch << ' ' << s2[curj] << endl;
                ++curi;
                ++curj;
                break;
            }
        case 2:
            {
                cout << "INSERT " << curi + ch << ' ' << s2[curj] << endl;
                ++curj;
                ++ch;
                break;
            }
        case 3:
            {
                ++curi;
                ++curj;
            }
        }
    }
    return 0;
}

Научиться программировать

  • на Delphi

  • на Java

  • на C++