مسئله 95 - صفحه 95 کتاب «مسئله‌های الگوریتمی»: تبدیل رشته

دو رشته‌ی u و v داده شده‌اند. می‌خواهیم با حداقل تعداد اعمال زیر u را به v تبدیل نماییم:
  - :delete(i) حرف در موقعیت i را حذف کن.
  - :add(i,'x') حرف x را در موقغیت بعد از i اضافه کن.
  - :change(i,'x') حرف در موقعیت i را به x تغییر بده.

برای مثال می‌توانیم رشته‌ی abbac را به رشته‌ی abcbc با سه عمل تبدیل نماییم (که البته این تعداد اعمال حداقل نیستند):

abbac ---> abac ( delete(2) )
      ---> ababc ( add(3,'b') )
      ---> abcbc ( change(3,'c') )

برنامه‌ای بنویسید که با دریافت دو رشته‌ی u و v، رشته‌ی u را با کمترین تعداد اعمال به v تبدیل کند. در سطر اول فایل ورودی رشته‌ی u و در سطر دوم رشته‌ی v نوشته شده‌است. خروجی مانند مثال زیر است:

1#include <iostream>
2#include <fstream>
3#define MAX 20
4using namespace std;
5void FindMinOperations(int C[MAX][MAX], char S1[MAX], int L1, char S2[MAX], int L2, char OP[MAX][MAX]) {
6  for (int I = 0; I <= max(L1, L2); I++)
7    C[0][I] = C[I][0] = I, OP[0][I] = 'D', OP[I][0] = 'A';
8  for (int ROW = 1; ROW <= L2; ROW++)
9    for (int COL = 1; COL <= L1; COL++) {
10      if (S1[COL - 1] == S2[ROW - 1])
11        C[ROW][COL] = C[ROW - 1][COL - 1], OP[ROW][COL] = 'E';
12      else
13        C[ROW][COL] = C[ROW - 1][COL - 1] + 1, OP[ROW][COL] = 'C';
14      if (C[ROW - 1][COL] + 1 < C[ROW][COL])
15        C[ROW][COL] = C[ROW - 1][COL] + 1, OP[ROW][COL] = 'A';
16      if (C[ROW][COL - 1] + 1 < C[ROW][COL])
17        C[ROW][COL] = C[ROW][COL - 1] + 1, OP[ROW][COL] = 'D';
18    }
19}
20void ModifyString(char OP[MAX][MAX], int ROW, int COL, char S1[MAX], char S2[MAX]) {
21  if (OP[ROW][COL] == 'C')
22    S1[COL - 1] = S2[ROW - 1];
23  else if (OP[ROW][COL] == 'A') {
24    for (int I = strlen(S1) + 1; I >= COL; I--)
25      S1[I] = S1[I - 1];
26    S1[COL] = S2[ROW - 1];
27  }
28  else if (OP[ROW][COL] == 'D') {
29    int L1 = strlen(S1);
30    for (int I = COL - 1; I < L1; I++)
31      S1[I] = S1[I + 1];
32  }
33}
34void PrintOperations(char OP[MAX][MAX], int& ROW, int& COL, char S[MAX], fstream* OUT) {
35  if (OP[ROW][COL] == 'C') {
36    *OUT << "( change(" << COL << ",'" << S[ROW - 1] << "') )" << endl;
37    ROW--;
38    COL--;
39  }
40  else if (OP[ROW][COL] == 'A') {
41    *OUT << "( add(" << COL << ",'" << S[ROW - 1] << "') )" << endl;
42    ROW--;
43  }
44  else if (OP[ROW][COL] == 'D') {
45    *OUT << "( delete(" << COL << ") )" << endl;
46    COL--;
47  }
48}
49int main() {
50  char S1[MAX], S2[MAX], OP[MAX][MAX] = { 0 };
51  int C[MAX][MAX] = { 0 }, L1, L2, ROW, COL;
52  fstream IN, OUT;
53  IN.open("INPUT.TXT", ios::in);
54  IN.getline(S1, MAX);
55  IN.getline(S2, MAX);
56  L1 = strlen(S1), L2 = strlen(S2);
57  FindMinOperations(C, S1, L1, S2, L2, OP);
58  OUT.open("OUTPUT.TXT", ios::out);
59  OUT << C[L2][L1] << endl;
60  ROW = L2, COL = L1;
61  OUT << S1 << endl;
62  while (ROW > 0 || COL > 0)
63    if (ROW >= 0 && COL >= 0 && OP[ROW][COL] == 'E')
64      ROW--, COL--;
65    else {
66      ModifyString(OP, ROW, COL, S1, S2);
67      OUT << S1 << " ";
68      PrintOperations(OP, ROW, COL, S2, &OUT);
69    }
70  IN.close();
71  OUT.close();
72  return 0;
73}