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

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

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

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

#include
#include
#include
#include
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 <

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

  • на Delphi

  • на Java

  • на C++